Algorithm116 [Kotlin] 백준 14698 : 전생했더니 슬라임 연구자였던 건에 대하여(Hard) 문제 링크 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 문제 해설 각 테스트 케이스마다 구해야 하는 총 비용은 매 합성 단계마다 필요한 전기 에너지, 즉 매 합성 단계마다 합성되는 슬라임의 에너지들을 모두 곱한 값과 같다. 이 값을 최소로 하기 위해서는 매 합성마다 에너지가 가장 낮은 슬라임 둘을 합성해야 하는데, 예제의 경우를 그림으로 표현하면 다음과 같다. 따라서 우선순위 큐를 사용하면 문제를 수월하게 풀 수 있다. 입력받은 모든 슬라임을 우선순위 큐에 삽입한다... 2023. 2. 12. [Kotlin] 백준 11637 : 인기 투표 문제 링크 11637번: 인기 투표 각 테스트 케이스는 첫 번째 줄부터 순서대로 출력된다. 최다 득표자가 과반수 득표를 했을경우에는 "majority winner R", 절반 이하의 득표를 하였을 경우엔 "minority winner R"가 되며, 최다 득표자가 없 www.acmicpc.net 문제 해설 간단한 구현 문제이다. 각 테스트 케이스마다 매 입력으로 주어지는 득표 수 중 최대치와 득표 수의 합계를 구한다. 최대 득표 수의 개수가 1이 아니면(= 최다 득표자가 2명 이상이면) "no winner"를 출력한다. 최대 득표 수의 개수가 1이라면 득표 수의 합계를 2로 나눈 값과 최대 득표 수를 비교하여 "majority winner R" 또는 "minority winner R"를 출력한다. Code.. 2023. 2. 8. [Kotlin] 백준 12931 : 두 배 더하기 문제 링크 12931번: 두 배 더하기모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주www.acmicpc.net문제 해설문제는 모든 값이 0으로 채워진 배열을 입력으로 주어진 배열로 만드는 것이지만, 역으로 생각해보면 입력으로 주어진 배열의 모든 값을 0으로 만들기 위한 연산의 최소 횟수를 구하는 문제라는 것을 알 수 있다. 역으로 접근하면 된다는 것을 알았으니 어떻게 연산을 진행할 지 생각해보자. 배열의 모든 값을 반으로 나누는 것이 값 하나를 1 감소시키는 것보다 훨씬 효율적이다. 그런데 홀수는 반으로 나눌 수 없으니 1 .. 2023. 2. 5. [Kotlin] 백준 1629 : 곱셈 문제 링크 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 해설 \(A^B\mod C\)를 구해야 한다. 그런데 \(A\), \(B\), \(C\) 모두 최대치가 Int.MAX_VALUE이기 때문에 정말 정직하게 거듭제곱을 하면 무조건 시간초과가 발생한다. 따라서 효율적인 방법을 찾아서 해결해야 한다. 이 문제는 지수 법칙을 이용하면 수월하게 해결할 수 있다. \(x^{2n}=(x^2)^n\)인 성질과 \(x{n+m}=x^n\times x^m\)인 성질을 이용하여 지수를 계속 반으로 나누면서 밑을 제곱하는 것이다. 예를 들어 \(2^{14}\)를 지수 법칙을 이용해서 .. 2023. 2. 2. [Kotlin] 백준 25306 : 연속 XOR 문제 링크 25306번: 연속 XOR 3에서 5까지의 자연수는 3, 4, 5로, 세 개 존재한다. 세 수를 XOR한 값은 (3 XOR 4) XOR 5 = 7 XOR 5 = 2 이다. www.acmicpc.net 문제 해설 \(A\)와 \(B\)가 최대 \(10^{18}\)이기 때문에 하나씩 차근차근 XOR 연산을 하면 시간 초과가 발생한다. 이 문제를 시간 내에 해결하기 위해선 누적 XOR의 성질을 알 필요가 있다. \(1\leq N\leq 100\)인 \(N\)에 대하여 각 구간별로 누적 XOR을 구해보면 다음과 같은 결과를 얻을 수 있다. 결과를 잘 보면 \(N\)을 4로 나눈 나머지의 값에 따라 규칙적으로 결과가 변한다는 것을 알 수 있다. 1 → 1 2 → \(N+1\) 3 → 0 0 → \(N\.. 2023. 1. 29. [Kotlin] 백준 23300 : 웹 브라우저 2 문제 링크 23300번: 웹 브라우저 2 첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 가 각각 주어진다.(1 ≤ N, Q ≤ 2,000) 둘째 줄부터는 Q개의 작업이 주어지며, 각 작업이 의미하는 바는 다음 www.acmicpc.net 문제 해설 뒤로가기 목록을 저장할 스택과 앞으로가기 목록을 저장할 큐를 각각 만들면 손쉽게 해결할 수 있다. 본 코드에서는 덱을 사용했지만 크게 상관은 없다고 생각한다. 압축 기능은 뒤로가기 목록의 2번째 페이지부터 마지막 페이지까지 이동하면서 이전 페이지와 같으면 제거하는 식으로 구현했다. Code import java.util.StringTokenizer fun main() = with(System.`in`.bufferedRe.. 2023. 1. 26. [Kotlin] 백준 26597 : 이 사람 왜 이렇게 1122를 좋아함? 문제 링크 26597번: 이 사람 왜 이렇게 1122를 좋아함? 질의응답에 모순이 없고 준성이의 최애 숫자가 무엇인지 정확히 알 수 있으므로 첫째 줄에 I got it!을 출력한다. $3$번째 질의응답을 통해 준성이의 최애 숫자가 무엇인지 정확히 알 수 있으므로 www.acmicpc.net 문제 해설 문제 자체는 평범한 Up&Down 방식의 문제다. 최초 시작값과 끝값을 각각 \(-10^{18}\)과 \(10^{18}\)으로 설정한다. 이후 질의응답에 따라 시작값과 끝값을 변경하는데, 질의 응답에서 주어지는 \(x\)가 기존 시작값보다 작거나 기존 끝값보다 클 수도 있다. 따라서 질의 응답이 \(x\) ^인 경우에는 시작값을 기존 시작값과 \(x+1\) 중 더 큰 값으로 변경하고, \(x\) v인 경우에.. 2023. 1. 25. [Kotlin] 백준 11444 : 피보나치 수 6 문제 링크 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해설 피보나치 수를 구하는 문제지만 입력이 굉장히 큰 경우다. 이 경우 피보나치 수를 구하는 일반적인 식인 \(F_n=F_{n-1}+F_{n-2}\)을 사용하게 되면 최대 \(10^{18}\)번의 연산을 수행해야 하기 때문에 이 방법은 사용할 수 없다. 문제를 해결하기 위해서는 더 효율적인 방법을 찾아야 하는데, 피보나치 수를 구하는 방법 중에는 도가뉴 항등식(d'Ocagne's identity)이라는 것이 있다. 도가뉴 항등식의 형태는 다음과 같다. $$F_{m+n}=F_{m-1}F_n+F_mF_{n+1}$$ 여기서 \(m.. 2023. 1. 24. 이전 1 ··· 4 5 6 7 8 9 10 ··· 15 다음
