문제 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 문제는 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 것이다. 반복문으로 해결하면 시간초과가 발생한다. 풀기 위해서는 지수 법칙과 모듈러 연산 성질에 대해 알고 있어야 한다. - 지수 법칙: $a^{(n+m)} = a^n \times a^m$ - 모듈러 연산 곱셈 성질: $(a\times b)\mod c = (a\mod c \times b\mod c)\mod c$ 이 두 성질을 활용하여 재귀 함수를 만들면 된다. 함수는 지수가 1이 될 때까지 B를 절반으로 나누어가며 계산한다. - 지수가 짝수인 경우 $a^n = ..

문제 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP(동적 프로그래밍)으로 해결하는 문제이다. 민규가 카드를 N개를 구매하는 방법은 여러가지가 있으며 다음과 같다. - 카드 1개가 포함된 카드팩 + 카드 N-1개 구매: price[1] + dp[N-1] - 카드 2개가 포함된 카드팩 + 카드 N-2개 구매: price[2] + dp[N-2] - 카드 3개가 포함된 카드팩 + 카드 N-3개 구매: price[3] + dp[N-3] ... - 카드 M개가 포함된 카드팩 + 카드 N-M개 구매(점화식): $d..

문제 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP(동적 프로그래밍)으로 해결하는 문제이다. 민규가 카드를 N개를 구매하는 방법은 여러가지가 있으며 다음과 같다. - 카드 1개가 포함된 카드팩 + 카드 N-1개 구매: price[1] + dp[N-1] - 카드 2개가 포함된 카드팩 + 카드 N-2개 구매: price[2] + dp[N-2] - 카드 3개가 포함된 카드팩 + 카드 N-3개 구매: price[3] + dp[N-3] ... - 카드 M개가 포함된 카드팩 + 카드 N-M개 구매(점화식): $dp[..

문제 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 풀이 입력받은 배열의 모든 지점에서 출발하는 DFS(깊이 우선 탐색)를 수행하고 각 DFS에서는 현재 위치에서 상하좌우도 이동하여 새로운 숫자를 만들어 나간다. DFS의 깊이가 6이 되면 탐색을 종료하고, 탐색으로 찾은 6자리 숫자를 HashSet에 저장한다. HashSet은 중복을 제외하기 기 때문에 HashSet의 크기는 탐색으로 발견 가능한 모든 수의 개수가 된다. 코드 fun main() { val br =..

문제 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 하노이의 탑 문제는 큰 부분을 작은 부분으로 나누어 해결하는 재귀적 접근으로 해결할 수 있다. 원판을 모두 목적지로 옮기기 위해서는 먼저 가장 큰 원판을 목적지로 옮겨야한다. 따라서 나머지 원판들을 목적지가 아닌 곳으로 옮긴다. 나머지 원판들을 모두 옮기고 나면 가장 큰 원판을 목적지로 옮기고 그 후에 나머지 원판들을 목적지로 옮기면 된다. 위의 과정은 재귀를 이용해 해결할 수 있는데, 두번째로 큰 원판 또한 목적지로 옮기기위해 나머지 원판들을 목적지가..