풀이
n=int(input())
dp=[0] *(n+1)
for i in range(2, n+1):
dp[i]=dp[i-1]+1
if i%3==0:
dp[i]=min(dp[i], dp[i//3] +1 )
if i%2==0:
dp[i]=min(dp[i], dp[i//2] +1 )
print(dp[n])
해석
DP를 공부하고 처음 관련 문제를 풀어보고자 했던 문제인데 작은 값들이 반복적으로 쓰인다는 느낌은 왔지만 코드로는 잘 안짜져서 답답했다..다른 사람들의 코드를 참고한 뒤 코드 이해 후 나도 쉽게 짜지는 그날까지..열심히 하고자 한다.
이 문제는 DP의 하향식으로 작성하는게 더 간단하다.
코드를 해석해보면
처음 값을 받고, 소문제 결과를 저장할 리스트, 즉 2일때 최소 연산 횟수, 3일때 최소 연산 횟수를 저장할 리스트를 만든다 (= 메모이제이션 할 리스트)
n=int(input())
dp=[0] * (n+1)
#n+1을 한 이유는 dp[1]은 첫번째 수로, dp[2]는 두번째 수로 생각하기 위해서 이다. (계산하기 편함을 위해서)for문을 통해 2부터 n 값까지 배열에 횟수를 넣어준다. 즉 2일 때의 최소 연산 횟수 계산해주고, n일 때의 최소 연산 횟수까지 계산해주어야지 값이 나오기 때문이다.
=> 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하기 위해 for문을 사용한다.
문제에서
- (1을 빼는 방법)
- (2를 나누는 방법)
- (3을 나누는 방법)
중에서 가장 최소 연산 횟수가 무엇인지를 고려해야 한다
무조건 나눈다고 최소 연산 횟수는 아니다.
ex) 10의 최소 연산 횟수를 구하고자 할 때
나누는 방법을 우선시 했을 경우, 10-5-4-2-1 으로 4번이나 연산 횟수가 일어나야한다.
하지만 처음 10에서 1을 빼면 10-9-3-1로 3번의 연산 횟수가 일어난다. 즉 3이 출력되어야 한다는 것이다.
이 문제가 DP인 이유는
- 2-1 (1)
- 3-1 (1)
- 4-2-1 (2)
- 5-4-2-1 (3)
- 6-3-1 / 6-2-1 (2)
- 7-6-3-1 / 7-6-2-1 (3)
...
와 같이 작은 소문제가 반복되기 때문이다.
dp 배열에는 (0, 0, 1, 1, 2, 3, 2, 3, ..) 이렇게 들어간다.
for문 안 코드를 살펴보면
dp[i]=dp[i-1]+1
if i%3==0:
dp[i]=min(dp[i], dp[i//3] +1 )
if i%2==0:
dp[i]=min(dp[i], dp[i//2] +1 )이렇게 되어있다.
dp[i]=dp[i-1]+1 의 경우에 dp[i-1]가 앞서 계산된 최소연산 횟수인데 앞선 수에 대한 연산횟수에 (앞서 말한, 1을 빼는 방법)을 했다고 생각해서 1번의 연산이 일어난 것이기 때문에 +1을 더한 것이다. 무작정 1을 빼는 방법을 먼저 수행해놓고 본것이다! 이후에 이 방법이 작은 경우의 수를 만들게 한 것인지는 min()함수를 써서 비교할 것이기 때문이다!
if문으로 3으로 나누어 떨어지는지 2로 나누어떨어지는 지를 본다. 이때 if/elif/else 방법을 쓰면 안된다.
3으로 나누어 진다면, (1을 빼는 방법)이 더 적은연산횟수를 갖게 된것인지, (3을 나누는 방법)이 더 적은연산횟수를 갖게 된것인지를 비교해서 더 작은 방법을 갖게 된다!
여기에서도 dp[i//3] + 1에 1을 더하는 이유는 (2를 나누는 방법)을 써서 추가되는 연산횟수이다. 이전에 (1을 빼는 방법)을 써서 발생한 연산횟수에 대해 더해주는 것과 같은 느낌이다!!
ex) 6일 때를 계산해보자
dp[6]=dp[5]+1 //3+1 => dp[6]=4 #(1을 빼는 방법)
if(i%3)==0:
dp[i]=min(dp[i], dp[i//3] +1 ) //min(4, 1+1) => dp[6]=2
=> 4에서 2로 더 작은 연산 횟수로 바뀐 것을 볼 수 있음코드는 이런 구조로 돌아가 결과를 출력할 수 있다.
참고 코드
DP 문제 더 풀어서 감 잡아야겠다!! 아직까지는 어렵다는 생각이 든다..ㅠ
