문제 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 풀이 하노이의 탑 문제는 큰 부분을 작은 부분으로 나누어 해결하는 재귀적 접근으로 해결할 수 있다. 원판을 모두 목적지로 옮기기 위해서는 먼저 가장 큰 원판을 목적지로 옮겨야한다. 따라서 나머지 원판들을 목적지가 아닌 곳으로 옮긴다. 나머지 원판들을 모두 옮기고 나면 가장 큰 원판을 목적지로 옮기고 그 후에 나머지 원판들을 목적지로 옮기면 된다. 위의 과정은 재귀를 이용해 해결할 수 있는데, 두번째로 큰 원판 또한 목적지로 옮기기위해 나머지 원판들을 목적지가..

문제 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 병든 나이트는 오른쪽 위나 아래로만 움직일 수 있으며 4칸 이상 방문한 경우에는 모든 방향으로 최소 한 번은 움직여야 하기 때문에 체스판의 크기에 따라 움직임이 제한된다. - N = 1 아무 방향으로 움직일 수 없기 때문에 답은 1이다. - N = 2 2번과 3번 방향으로만 움직일 수 있기 때문에 답은 (M+1)/2이다. 그러나 최대 4칸까지만 이동이 가능하다. - N >= 3 1) M < 7: 1번과 4번 방향을 번갈아가면서 이동하는 것이 최대로 방문하는 방법이다. 따라서 답은 M이다. 그러나 최대 4칸까지만 이동..