백준/ class3 문제 , 백준 파이썬 1463 , 1로 만들기 , dp 문제

백준/ class3 문제 , 백준 파이썬 1463 , 1로 만들기 , dp 문제

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
실버 3 문제치고는 어려운 편에 속하는 문제 같음. 시간초과, 런타임에러랑 싸우다가 겨우겨우 풀어냈다.
시간제한 때문에 단순 중첩 반복문으로는 풀수없고, dp 를 사용해 시간복잡도를 O(n) 으로 만들어 풀어내야한다.

 

 

 

 

<문제 출처>

 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

------------------------------------------------------------------------------------------------------------------------------

 

<문제 풀이>

 

 

우선 문제의 조건들을 확인해보자.

 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

 

이 세가지 수행중 각 상황에 맞는걸 택하여 최소한의 수행으로 1을 만들어 주면 된다.

 

 

우선 정해지는 숫자들이 있다.

 

바로 인덱스 3까지의 값들인데, 편의를 위해서 인덱스 0자리에 0 을 추가해 자릿수를 맞춰주자.

 

index	0	1	2	3
값	0	0	1	1

 

이렇게 정해진다.

 

1은 수행할 필요가 없으니 0 

2는 2로 나누어 주면 1이 되니 1

3은 3으로 나누어 주면 1이 되니 1

 

 

하지만 주의할 점은

 

 

초기값을 이렇게 주고 시작하면

 

 

 

이렇게 런타임 에러가 발생한다.

 

그러니 초기값을 따로 설정해주지 않고 for 문을 2 부터시작해주면 된다.

 

 

 

 

인덱스 2의 자리부터 연산을 시작하면 전 인덱스 1의 자리의 값보다 1을 우선 더해준다.

 

for 문 내에서 반복을 할때마다 전 인덱스 자릿값의 값에서 1을 더해준뒤 초기값을 설정해줄 건데,

 

이것은 조건 중에 3. 1을 뺀다.   이 조건때문에 그렇다.

 

만약 값이 2나 3으로 나누어지지 않는다면 1을 빼준뒤 2나 3으로 나누어지는지 확인을 해야할텐데

 

이 과정에서 이미 한번의 조건이 사용 되었기때문이다.

 

그러니 그 수에서 발생할 수 있는 최대의 수행 값을 우선적으로 부여하는 것이다.

 

 

더 쉽게 알기 위해 예를 들어보자.

 

6은 총 2번의 최소 연산 수행과정을 거친다. 2랑 3으로 각각 한번씩 나누어주면 되기때문이다.

 

(6 //2) //3 == 1 => 총 2번

 

 

그렇다면 다음 수 7은?

 

7은 2나 3으로 나누어지지않는다.

 

그러니 1을 빼주어야한다. 그러니 조건 3이 수행되어 1번의 연산을 더해야한다.

 

1을 빼서 만든 6에서 총 2번의 수행으로 1을 만들었으므로 총 3번의 수행과정이 7에서 발생한것이다.

 

 

더이상 최소한의 수행 과정의 없으므로 7은 3의 값을 갖는다.

 

 

그렇다면 7의 다음수 8은 1을 더한 4의 값을 가질까?

 

확인해보자.

 

 

우선적으로 8에게 4의 값을 부여한다. 8에서 1을 빼서 7을 만든다는 식으로 수행과정을 거치면 나올 수 있는 수행 과정은 총 4가지이기때문이다.

 

8 -1 -1 //2 // 3 ==1  => 총 4가지

 

하지만 이게 최소 수행 횟수가 아니라는 것이다.

 

8은 2로 나누어지므로 인덱스 4의 자리 값을 불러올 수 가 있다.

 

4는 총 2번의 연산으로 1로 만들 수 있으므로 2의 값을 가지고있다.

 

이 2의 값을 불러오고 8에서 2를 한번 나누어 줬으므로 1번의 수행값을 더 더해줘서

 

총 3번의 수행값을 갖는다. 이 수행값은 위의 4번의 수행값보다 작으므로 8은 3의 최소 수행 값을 갖는다.

 

 

 

여기까지의 원리가 이 문제를 풀어가는 원리이다. 

 

1. 전 인덱스의 값에서 1을 더해줘 값을 우선적으로 부여

 

2. 그 값이 최소값인지 확인 하는 과정

 

이 두가지가 필요한 것이다. 1번이 최소면 그 인덱스값은 1번의 값을 가져가고 만약 2번에서 최솟값이 나오면 2번의 값을 가져간다.

 

 

 

 

이것을 일반화시켜 코드를 작성하면

 

dp(n) = min( dp(n-1), dp(n//2)+1, dp(n//3)+1) 이렇게 될 것이다.

 

우선적으로 값을 부여하려면

 

 

이렇게 전 인덱스 값에 1을 더해준다.

 

이후 값을 비교하는 과정을 거치면

 

 

 

이렇게 작성하면 되겠다.

 

만약 2나 3으로 나누어지는데 그 값이 위에서 우선적으로 부여한 값보다 작다면 그 값을 가져가고, 아니라면 우선적으로 부여한 값 그대로 가져가는 것이다.

 

 

이 연산은 N 까지 수행 되므로 시간 복잡도 O(n) 이 나오는 연산인것도 알 수 있다.

 

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

정답