처음 생각한 풀이
우선 1~3까지는 횟수가 1번으로 정해져 있으므로 1로 dp 배열에 넣고 4부터 2로 나누어지면 2로 나눈 숫자의 횟수에 1을 더하고 3으로 나누어지면 3으로 나눈 숫자의 횟수에 1을 더한다 2, 3 둘다 나눠 지지 않으면 이전 숫자의 횟수에 1을 더하는 방식으로 한다.
n = int(input())
dp = [0, 0, 1, 1]
for i in range(4, n+1):
if i % 3 == 0:
dp.append(dp[i//3]+1)
elif i % 2 == 0:
dp.append(dp[i//2]+1)
else:
dp.append(dp[i-1]+1)
print(dp)
print(dp[n])실행결과
실행결과를 확인했을 때 2,3으로 나누어지더라도 이전 숫자의 횟수가 적으면 이전 숫자에서 1을 더하는 방식이 적을 수 있으므로 이전 숫자나 나누어 졌을 때의 횟수 비교가 필요하다는 것을 깨달음
수정 코드
n = int(input())
dp = [0, 0, 1, 1]
for i in range(4, n+1):
if i % 3 == 0:
dp.append(min(dp[i//3], dp[i-1]) + 1)
elif i % 2 == 0:
dp.append(min(dp[i//2], dp[i-1]) + 1)
else:
dp.append(dp[i-1]+1)
print(dp)
print(dp[n])여러 테스트 결과 정답처럼 보여서 제출했지만 백준에서는 틀렸다고 한다.
생각해 봤을 때 2와 3의 최소 공배수 즉 6으로 나누어 떨여질때는 2와 3중 어떤 것으로 나눌때가 최소인지 구분하는것도 필요하다고 생각
수정 코드
n = int(input())
dp = [0, 0, 1, 1]
for i in range(4, n+1):
if i % 6 == 0:
dp.append(min(dp[i//3], dp[i//2], dp[i-1]) + 1)
elif i % 3 == 0:
dp.append(min(dp[i//3], dp[i-1]) + 1)
elif i % 2 == 0:
dp.append(min(dp[i//2], dp[i-1]) + 1)
else:
dp.append(dp[i-1]+1)
print(dp[n])드디어 정답
다른사람 코드와 비교
n = int(input())
d = [0] * 1000001
for i in range(2, n+1):
d[i] = d[i-1] + 1
if i % 2 == 0:
d[i] = min(d[i], d[i//2] + 1)
if i % 3 == 0:
d[i] = min(d[i], d[i//3] + 1)
print(d[n])해당 인덱스를 이전 인덱스에서 1을 더한 값을 먼저 지정한 후 if ~elif가 아닌 if문으로 2, 3으로 나눠지는 경우를 설정 했기 때문에 6으로 나눠지는 경우도 따로 작성할 필요 없다.... 한 수 배웠습니다
ㄱH ㅂrㄹ ㅈr