https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제풀이 위 문제는 거스름돈 5원과 2원으로 주어진 돈을 거슬러 줘야 하는데 이때 동전을 최소한으로 사용하여 거슬러 줘야 한다. 먼저, 15원까지 동전의 수를 나열해 보았다. 나열해 본 결과 반복되는 패턴이 있음을 알 수 있다. 주어진 돈이 5의 배수가 아니면 주어진 돈 n 원에 대한 동전의 개수는 n - 2원에 대한 동전의 개수 + 1인 것을 알 수 있었다. 때문에 위 문제는 다이내믹 프로그래밍을 활용하여 문제를 해결할 수 있다. var n = Int(readLine()!)! var result = 0 var dp..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이과정 문제를 정리하면, 계단마다 점수가 있다. 계단은 1칸 혹은 2칸씩 오를 수 있다. 하지만, 연속된 세 개의 계단을 모두 밟을 수는 없다. 이때 얻을 수 있는 점수의 최댓값을 구해야 한다. 중요한 키워드만 정리해 보았다. 해당 문제는 DP를 활용하여 풀 수 있다. 각 계단을 올랐을 때 포인트의 최댓값을 알고 있으면 해당 포인트에 앞으로 오를 계단의 포인트를 더해주면 해결할 수 있다. 계단 수가 1번부터..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이과정 먼저, 몇가지 수를 직접 계산해 보았다. 정수 N의 범위는 [1 1 이기 때문에 => 1 3은 3/3 =1 -> 1 이기에 => 1 4는 4/2 = 2 -> 2/2 = 1 -> 1 => 2 5는 5 -1 = 4 -> 4/2 = 2 -> 2/2 = 1 -> 1 => 3 6은 6/3 = 3 -> 3/3 = 1 -> 1 => 2 이정도면, 규칙성이 보인다. 1, 2, 3은 각 0, 1, 1이고, 4부터는 2또는 3으로 나누거나 빼기 1을 하면 미리 계산했던 값이 되는것을 알 수 있다. 규칙성을 좀더 한눈에 ..