이 문제는 이전 문제였던 설탕 배달이 생각보다 빨리 끝나서 그 날에 한문제 더 풀어버린 문제이다.
바로 따라란
뭔가 이거 멋 없는데-이거 누르면 됨
이 문제다!!!
1로 만들기!! 첫번째 글처럼 문제를 말로 설명하니까 뭔가 난해해서 살짝 깔끔하게 해보겠다.
문제
정수 N이 주어졌을 때 이 정수에 사용할 수 있는 연산은 세가지임.
1. N이 3으로 나누어 떨어지면 3으로 나눔.
2. N이 2로 나누어 떨어지면 2로 나눔.
3. 1,2 둘다 아니면 1뺌.
좀 깔끔한가? 그냥 저번꺼랑 다르게 문제가 이해하기 쉬워서 그런가..
암튼 예를 들어 10 이 있으면
10->5->4->3->1 이런 식이나 10->9->3->1 이런 식으로
1로 만들었을 때 연산이 가장 적은 거 찾으면 된다!
기본적인 생각은 솔직히 말하면 이거 생각했을 때 천잰 줄 알았다.
나도 어떻게 그랬는지는 모르겠는데 갑자기 번뜩 생각났다.
N이 있을 때 N의 이전 단계는 3가지가 될 수 있다.
1) N이 3으로 나누어져서 N이 3으로 나누어진 상태
2) N이 2로 나누어져서 N이 2로 나누어진 상태
3) N에서 1 뺀 상태
이 셋 중에 min 값 찾으면 끝이다!
그 min값에서 1만 더하면 우리가 찾는 최소값이다! - min(이전 단계) + 1(현재)
이것도 저번 꺼랑 마찬가지로 바름업(bottom up)방식으로 차근차근 올라가면 된다.
⌨그럼 코드를 보자
X = int(input())
dp = [0,0,1,1]
if X > 3:
for i in range(4,X+1):
dp.append(dp[i-1]+1)
if i % 3 == 0:
dp[i] = min(dp[i//3]+1, dp[i])
if i % 2 == 0:
dp[i] = min(dp[i//2]+1, dp[i])
print(dp[X])자 dp배열의 인덱스는 우리가 찾고자하는 N값이고 각각의 값들은 N을 1로 만들었을 때 최소의 수이다.
먼저 1,2,3 의 값들을 넣어주고 시작했다.
그리고 4부터는 배열에 append로 추가해줬다.
for문 함 보자
먼저 아까 N의 이전 단계 중 3번째 상태에 +1 한 경우를 append 해줬다.
-> dp[i-1] + 1 로 일단 fix해놓고 다른 상태들이랑 비교한다는 뜻
그리고 그 상태와 3으로 나누었을 때랑 2로 나누었을 때 비교해서 더 작은 값 넣어줬다.
이렇게 한 이유는 뒤에 처음에 짰던 틀린 코드를 보면서 설명하겠다.
X = int(input())
dp = [0,0,1,1]
if X > 3:
for i in range(4,X+1):
if i % 3 == 0:
dp.append(min(dp[i//3]+1, dp[i-1]+1))
elif i % 2 == 0:
dp.append(min(dp[i//2]+1, dp[i-1]+1))
else:
dp.append(dp[i-1]+1)
print(dp[X])처음에는 이렇게 진짜 직관 적으로 3가지 조건을 걸어서 비교해서 넣었는데 이러면 예외 케이스가 발생하는 것 같다... 더 자세한 건 나중에 더 분석해보도록 하겠다.
쓰다가 중간에 살짝 분석해봤는데 그냥 안되는 것 같다. 갑자기 번뜩이면 그때 다시 수정하도록 하겠다.
🚄흐름을 읽어보자
4부터 시작,
2로 나누어지니까 2(4//2)랑 3(4-1)이랑 비교 했을 때 둘다 1이니까 dp[4] = 1+1
5일때,
안나눠짐 -> dp[5] = dp[5-1]+1 = 3
6일때,
dp[6] = dp[6//2]+1 = dp[6//3]+1 = 2
7일때,
dp[7] = dp[7-1]+1 = 3
8일때,
dp[8] = min(dp[8//2]+1, dp[8-1]+1) = min(3,4) = 3
9일때,
dp[9] = min(dp[9//3]+1, dp[9-1]+1) = min(2,4) = 2
10일때,
dp[10] = min(dp[10//2]+1, dp[10-1]+1) = min(4,3) = 3
요런식이다
Reivew
운좋게 아이디어가 금방 생각나서 빨리 푼 문제이다. 뭔가 같은 풀이로만 계속 푸는 것 같은 느낌인데, 다른 풀이로도 풀리는 지 좀 더 고민해보고 풀어봐야겠다.
뭔가 흐름을 읽고 코드를 보는 게 문맥상 맞는 거 같다;; 이제 그렇게 해야겠다. 너무 내 입장에서만 썼다... 나는 코드를 보는 상태에서 흐름을 읽으니까 술술 하는데 처음 보는 사람 입장에서는 좀 불편할 듯 ㅋ 근데 내꺼 보는 사람 있을랑가 뭔가 코딩괴수가 와서 잘못한 거 알려줄 거 같아
