[Python] 백준 1463번_1로 만들기

문제 

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

1463번: 1로 만들기

 

코드

mincal = [0,0]
num = int(input())

for i in range(2,num+1):
    mincal.append(mincal[i-1]+1)
    if i%3 == 0:
         mincal[i] = min(mincal[i], mincal[i//3]+1)
    if i%2==0:
         mincal[i] = min(mincal[i], mincal[i//2]+1)
print(mincal[num])

풀이 

처음에 if-elif를 이용했다가 오답이 나왔었다.

mincal = [0,0]
num = int(input())

if num == 1: #굳이 1인 경우를 나누어 생각할 필요가 없음
    print(mincal[1])
else:
    for i in range(2,num+1):
        if i%2 == 0:
            minum = min(mincal[i-1], mincal[i//2])+1
        elif i%3==0: #if-elif를 사용할 경우, 2와 3 모두 가능한 경우 1가지 방향으로만 실행되므로 오답 발생
            minum = min(mincal[i-1], mincal[i//3])+1
        else:
            minum = mincal[i-1]+1
        mincal.append(minum)
    print(mincal[num])

따라서 위에서 num이 1인지 판별하는 부분을 삭제하고, mincal list에 -1로 시작하는 횟수를 계산한 값을 append 한다.

만약 2, 3으로 나눠지지 않는 값이라면 이 값이 그대로 갈 것이고, 2나 3, 혹은 2와 3 둘다로 나눠지는 값이라면 -1을 했을 때 값과 2(or 3)으로 나눴을 때 값 중 최소값으로 갱신된다.

인덱스가 주어진 수를 나타내며, 계산 횟수를 리스트에 누적시킴으로써 불필요한 계산을 줄인다.

예를 들어 5가 주어졌을 경우, 5에서 1을 빼면 (+1) 그 결과로 나오는 4의 연산 횟수는 minum[4]의 값이다.

따라서, minum[5]는 1+ minum[4]로 나타낼 수 있는 것이다.

반대로, 9가 주어졌을 경우, 9-1(+1)의 결과인 8의 연산횟수인 minum[8], 즉 minum[8]+1이 먼저 append되며,

2나 3으로 나눌 수 있는지 시도한다. 이때 3으로 나눌 수 있으므로 minum[9//3], 즉 minum[3]+1(//3 함)이 그 값이된다. 

개선점

• 배열을 먼저 생성해두고 하는게 더 편리할 것 같다 (더 직관적이고 접근 쉬움)

mincal = [0] * (n+1)
num = int(input())

for i in range(2,num+1):
    mincal[i] = mincal[i-1] + 1
...

다른 풀이 

 출처: https://www.acmicpc.net/source/18527657

l={int(input())} #set생성, element는 입력 값
n=0
while 1 not in l: #1이 set l안에 없을 경우 break
	t=set() #빈 set 생성
    n+=1
	for i in l:
		if i%3==0:
        	t.add(i//3)
		if i%2==0:
        	t.add(i//2)
		t.add(i-1)
	l=t
print(n)

→ 리스트 대신 세트를 사용해서 속도를 높였다. 

• DP의 핵심은 메모이제이션 방법을 사용해 중복 계산을 최소화 함으로써 효율을 올리는 것이다.