![[Python] 백준 1463: 1로 만들기 풀이 [Python] 백준 1463: 1로 만들기 풀이](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
소스코드
n = int(input())
#인덱스와 일치하는 정수를 1로 만들기 위한 횟수의 최솟값
dp = [0,0,1,1]
for i in range(4,n+1):
# 1을 만들기까지 최대 횟수로 초기
dp.append(i-1)
# 1을 뺄 때의 최솟값
dp[i] = dp[i-1] + 1
# 2로 나누어 떨어질 때
if i % 2 == 0 :
# 1을 뺄 때와 2로 나눌 때 더 작은 횟수인 것을 저장
dp[i] = min(dp[i], dp[i//2] + 1)
if i % 3 == 0 :
# 앞에서 구한 arr[i]과 3으로 나눌 때 더 작은 횟수인 것을 저장
dp[i] = min(dp[i], dp[i//3] + 1)
print(dp[n])
처음 풀어보는 DP 문제라 조금 당황하긴 했다. 그래서 처음엔 단순하게 3으로 나누기,2로 나누기,1 빼기 순으로 연산 횟수가 작을 것이라고 생각하고 while 문에서 저 순으로 if ~ else 문을 작성하여 풀었더니, 당연히 틀렸다. 예제 입출력의 10 이 반례였다.
내가 생각한 단순한 로직으로는 10->5->4->3->1 로 4번의 연산이 필요한데,
10에서 먼저 1을 빼고 시작하면 10->9->3->1 로 3번의 연산이 필요하다.
즉, 각각의 단계에서 모든 경우의 수를 비교해서 최솟값을 도출해 내는 Dynamic Programming 문제임이 확실해졌다!
만약 dp[10] 을 구한다면??
1) dp[9] + 1 → 9(10에서 1을 뺀 수)에서 1까지의 최소 연산 횟수 + 10에서 1을 빼는 연산 (1회)
2) dp[5] + 1 → 5(10에서 2로 나눈 수)에서 1까지의 최소 연산 횟수 + 10에서 2를 나눈 연산 (1회)
3) 10은 3으로 나눠지지 않으므로 패스
▶1번과 2번 중 최솟값을 dp[10] 에 저장한다!!!!
그러므로 작은 문제부터 해결해나가는 상향식 방법으로 문제를 해결해 나가야 한다.
이말인 즉슨, 작은 숫자 부터 n까지 dp값 ( 그 숫자에서 1까지 가는 최소 횟수) 를 차례로 구해야된다는 것이다.
먼저 dp list값을 초기해주었다. 0과 1은 신경쓰지 않아도 되므로 0, 2는 2->1 (2로 나누기) 로 1, 3도 3->1 (3으로 나누기) 로 1 으로 초기화하였다.
그리고 for문에서 i가 4부터 n까지 증가하면서 dp[i] 값을 채워나간다.
i값이 2 또는 3으로 나눠지지 않을 수도 있으므로 항상 1을 빼주는 경우의 수를 먼저 생각하고, 1을 빼준 값을 dp[i] 에 저장시켰다. 그런 다음, 2 또는 3으로 나눠진다면 그 때의 최솟값과 미리 저장된 dp[i] 값과 비교하여 최솟값을 찾아 최종으로 갱신한다.
.
.
.
파이썬은 교양 수업때 끄적거린게 전부고, 백준에서 알고리즘을 풀면서 그때그 때 동시에 익혀가고 있는 중이다.
따로 문법을 공부한 후에 알고리즘을 풀려면, 그런 날이 방학 안에 오지 않을 것 같아 그냥 바로 문제에 뛰어들었다.
확실히 문제를 풀면서 자연스럽게 익혀가는 문법들은 더욱 직관적이고 기억에 잘 남는다.
아직은 c나 java에 훨씬 익숙해서, 계속 java 스럽게 코드를 짜는 경향이 있는데,
다른 사람들의 파이썬 스러운 잘 짜여진 코드를 보고 계속해서 수정해나가는 중이다.
화이팅..!♡
'알고리즘 > 동적프로그래밍(DP)' 카테고리의 다른 글
[Python] 백준 11057번: 오르막 수 풀이 (0) | 2021.01.21 |
---|---|
[Python] 백준 10844번: 쉬운 계단 수 풀이 (0) | 2021.01.21 |
[Python] 백준 9095번: 1, 2, 3 더하기 풀이 (0) | 2021.01.21 |
[Python] 백준 11727: 2xn 타일링 2 풀이 (0) | 2021.01.20 |
[Python] 백준 11726번: 2xn 타일링 풀이 (0) | 2021.01.20 |
댓글