[Python] 백준 1463: 1로 만들기 풀이

 

소스코드

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 스럽게 코드를 짜는 경향이 있는데,

다른 사람들의 파이썬 스러운 잘 짜여진 코드를 보고 계속해서 수정해나가는 중이다.

화이팅..!♡