BOJ 1463번(1로 만들기) 문제 풀이

★ solved.ac 난이도 : S3

(작성 시점 기준)

---

[문제 본문 링크]

1463번: 1로 만들기

---

이 문제는 일반적인 동적 계획법(DP) 문제입니다.

먼저 크기가 100만 이상인 충분한 정수 배열을 만듭니다.

(배열의 이름은 dp로 설정하며, 이 배열에 정답을 계산해 저장합니다.)

입력이 1이면 연산이 필요하지 않으므로 정답은 0입니다. (dp[1] = 0)

2 이상의 입력에 대해서는 문제의 조건에 따라 3가지로 생각할 수 있습니다.

 

경우 1. x가 3으로 나누어 떨어지는 경우 3으로 나누기 : min(dp[x], dp[x/3]+1)을 계산합니다.

(여기에서 +1은 1번의 추가 연산을 의미합니다.)

경우 2. x가 2로 나누어 떨어지는 경우 2로 나누기 : min(dp[x], dp[x/2]+1)을 계산합니다.

경우 3. 그렇지 않은 경우 1을 빼기 : dp[x-1]+1을 계산합니다.

 

위 3가지 경우에서 계산된 결과 값 중에서 가장 작은 값을 dp[x]에 저장합니다.

최종적으로 dp[n]을 출력합니다.

---

[BOJ에서 코드 보기]

공유 소스 보기

---

★ 틀린 점이 있다면 알려주세요~!