[백준 알고리즘] 1463번: 1로 만들기 (Python)

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

1463번: 1로 만들기

 

소스코드

 

 

런타임 에러 뜬 코드(IndexError)

 

 

 

풀이

다이나믹 프로그래밍이라고 불리는 동적 계획법을 활용하여 풀 수 있는 문제입니다 !

 

dy라는 리스트에는 입력 받은 n을 1로 만들기 위한 최소 연산 횟수가 저장됩니다. 

(n+1)로 설정해준 이유는 리스트의 인덱스는 0부터 시작하기 때문에 1로 시작점을 잡기 위해서 입니다

 

dy[i] = dy[i-1] + 1

만약 다른 조건 없이 n을 1로 만드는 최소 연산 횟수를 구한다고 하면,

dy[1] = 0 (1을 1로 만들기 위한 연산횟수는 0회)

dy[2] = 1 (dy[i-1] + 1)

dy[3] = 2 (dy[i-1] + 1) ... 

이처럼 1씩 증가할 것입니다. 그 이유는 n을 1로 만들기 위해서 1씩 계속 빼주면 되기 때문입니다.

 

하지만 저희는 다른 조건들도 사용할 수 있습니다.

 

if i%2 == 0:

  dy[i] = min(dy[i],dy[i//2] + 1)

if i%3 == 0:

  dy[i] = min(dy[i],dy[i//3] + 1)

 

위의 조건은 n이 2나 3으로 나눠지면 나눌 수 있다는 조건입니다 !

만약 n이 4일때, 1씩 빼줘서 최소 연산을 구한다면 3일 것입니다. 하지만 2로 나눠지기 때문에 이를 이용한다면 최소 연산 횟수는 2가 될 것입니다. ( n//2 = 2,1번,  2-1 = 1, 2번)

이 때 저희는 두가지 최소 연산의 경우의 수를 가질 수 있고 min() 함수를 활용하여 더 작은 값을 선택해줘야 합니다. 

3으로 나눠질 때도 같은 방식입니다. 이렇게 최소 연산 횟수를 구해주시면 됩니다 !

 

런타임 에러

처음 코드를 짜고 실행시킬 때 런타임에러가 발생했는데, 저는 dy[1]일 때와 dy[2]일 때는 횟수를 각각 0과1로 알고 있기 때문에 반복문을 3부터 시작하였습니다. 

 

그 이유는 입력 값의 n의 범위가 1보다 크거나 같음. 즉 1이 들어올 수도 있기 때문입니다.

만약 1이 들어오게 된다면, 제가 선언한 dy[2] = 1이 indexError를 유발하게 됩니당 ㅎㅎ :)