문제https://www.acmicpc.net/problem/1463정수 `X`에 사용할 수 있는 연산은 세 가지가 있다.`X`가 3으로 나누어 떨어지면, 3으로 나눈다.`X`가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어지면, 위의 세 가지 연산을 적절히 사용해서 1을 만들 수 있는 최소 연산 횟수를 구해야 한다.1 ≤ `N` ≤ 1,000,000 풀이시간 제한이 0.15초로 매우 짧고, `N`의 범위를 보았을 때 브루트 포스 알고리즘을 적용하기 어렵다는 것을 알 수 있다.해당 문제는 DP(혹은 BFS)로 풀 수 있다. `N`이 10만 정도라면 DP로도 충분하다. 더 커지면 BFS를 사용할 수 있다. `dp[i]`를 정수 `i`에서 1로 만들기 위한 최소 연산 횟수로 정의한다.사용할..

문제https://www.acmicpc.net/problem/22250부터 `N`까지의 정수 `K`개를 더해서 그 합이 `N`이 되는 경우의 수를 구해야 한다.덧셈의 순서가 다를 경우(1+2와 2+1)는 다른 경우이고, 한 개의 수를 여러 번 쓸 수도 있다.1 ≤ `N` ≤ 2001 ≤ `K` ≤ 200답을 1,000,000,000으로 나눈 나머지를 출력해야 한다. 풀이브루트 포스로 풀기에는 N과 K가 너무 커서 DP로 접근하려고 했다.점화식을 어떻게 짜야할지 감이 잡히지 않아 30분 정도 고민하고 풀이를 봤다.일주일 뒤 꼭 다시 풀어볼 것. 점화식은 다음과 같이 짤 수 있다.숫자 `i`를 0부터 `n`의 숫자중에 `k`개를 이전 상태에서 더해나가는 식으로 `dp[k][n]`을 만든다. `dp[0][0..

문제https://www.acmicpc.net/problem/1535총 N명의 사람이 있다.사람과 악수를 하게 되면, 체력은 잃고 기쁨을 얻는다.체력은 100이며, 체력이 0이나 음수가 되지 않으면서 얻을 수 있는 최대의 기쁨을 구해야 한다. 풀이문제 자체는 0-1 배낭 문제와 같다. 하지만 평범한 배낭(https://www.acmicpc.net/problem/12865)보다는 인풋 값이 작아 다른 알고리즘을 시도해도 괜찮다. 알고리즘은 다음과 같다.cost[i]는 i번째 사람에게 잃는 체력, value[i]는 i번째 사람에게 얻을 수 있는 기쁨이다.dp[i][j]는 i번째 사람까지 고려했을 때, 체력을 j만큼 썼을 때의 최대 기쁨이다.현재 사람과 악수할 수 없는 경우(현재 체력보다 잃는 체력이 크거나..