💡 백준 1463: 1로 만들기
주어진 정수 X에 대하여 3으로 나누거나, 2로 나누거나, 1을 빼는 3가지 방법을 비교하여 그 중 최솟값을 찾아 최적해로 저장하여 계산
🌱 코드 in Python
알고리즘: Dynamic Programing
import sys
x = int(sys.stdin.readline())
dp = [0] * (x + 1) # 주어진 정수 x 만큼 배열 할당, 0으로 초기화
for i in range(2, x + 1): # 1은 연산의 횟수가 0이기 때문에 2부터 탐색
dp[i] = 1 + dp[i - 1] # 기본 값으로 전 항의 연산 횟수 + 1을 저장
if i % 3 == 0: # i가 3으로 나누어질 경우
dp[i] = min(dp[i], dp[i // 3] + 1) # 미리 저장해 둔 값과, i를 3으로 나눈 몫에 저장되어 있는 값 + 1을 한 값 중 더 작은 값을 저장
if i % 2 == 0: # i가 2로 나누어질 경우
dp[i] = min(dp[i], dp[i // 2] + 1) # 위의 결과와, i를 2로 나눈 몫에 저장되어 있는 값 + 1을 한 값 중 더 작은 값을 저장
print(dp[x]) # 정수 x의 연산 횟수 출력DP(Dynamic Programing)란, 메모이제이션 기법으로 한 번 계산했던 값은 다시 계산하지 않고 그 전에 구해두었던 최적해를 활용하는 알고리즘이다
이번 문제의 경우 최소 연산 횟수를 찾는 문제이기 때문에 역시 최적해를 찾는 방법을 사용하면 된다
1의 경우 연산 횟수가 0이므로 1을 제외하고 2부터 최적해를 저장해나가면 된다
정수 X에 대하여 1을 만들 수 있는 방법은 1) 3으로 나누거나 2) 2로 나누거나 3) 1을 빼는 3가지가 있다
따라서 X를 3으로 나누거나, 2로 나누거나, 1을 뺀 값의 최적해 + 1을 하면 X의 연산 횟수가 나오게 된다
- 위에서 3으로 나누어지는 경우와 2로 나누어지는 경우를 elif가 아닌 if로 준 이유는
i가 3으로도 나누어지고 2로도 나누어지는 경우,
즉 6의 배수일 때 많은 경우에 3으로 먼저 나누어 진행하는 것이 더 적은 연산 횟수를 가지지만,
때때로 2로 먼저 나누어 진행하는 것이 더 적은 연산 횟수를 가지는 경우가 있기 때문이다
👏 예를들어 642의 경우
1) 642 -> 214(/3) -> 107(/2) -> 106(-1) -> 53(/2) -> 52(-1) -> 26(/2) -> 13(/2) -> 12(-1) -> 4(/3) -> 2(/2) -> 1(/2): 11번
2) 642 -> 321(/2) -> 320(-1) -> 160(/2) -> 80(/2) -> 40(/2) -> 20(/2) -> 10(/2) -> 9(-1) -> 3(/3) -> 1(/3): 10번
2로 먼저 나누고 시작할 경우 3으로 먼저 나누고 시작한 경우보다 연산 횟수가 1회 적다
🧠 기억하자
이 짧은 코드를 두고 도대체 얼마나 많은 시간을 투자했던가?!
DP를 처음 접해보다보니 지금은 최소 어느 값까지의 기본 값을 구해놔야 하는가?가 조금 많이 헷갈린다
이 문제를 풀면서 처음 elif로 접근을 하며 많은 시행착오를 겪었다
import sys
n = int(sys.stdin.readline())
dp = [0] * 1000001
dp[1] = 0
dp[2] = 1
dp[3] = 1
for i in range(4, n + 1):
if i % 2 == 0:
dp[i] = 1 + min(dp[i // 2], dp[i - 1])
elif i % 3 == 0:
dp[i] = 1 + min(dp[i // 3], dp[i - 1])
else:
dp[i] = 1 + dp[i - 1]
print(dp[n])처음에는 이런식으로 접근을 했었는데, 조금 더 찾아보니 2와 3의 경우도 사실 구할 필요가 없었고
2로도, 3으로도 나누어지는 경우에 어떤 값이 최소인지 비교하지 않았던 것이 패착이었다
import sys
n = int(sys.stdin.readline())
dp = [0] * (n + 1)
for i in range(2, n + 1):
if i % 6 == 0:
dp[i] = 1 + min(dp[i // 2], dp[i // 3], dp[i - 1])
elif i % 2 == 0:
dp[i] = 1 + min(dp[i // 2], dp[i - 1])
elif i % 3 == 0:
dp[i] = 1 + min(dp[i // 3], dp[i - 1])
else:
dp[i] = 1 + dp[i - 1]
print(dp[n])상기 코드를 처음 elif의 문제를 깨닫고 이런식으로 고쳤었다가 조금 조잡해보여
약간의 써치^^ 후 가장 상단의 코드로 바꾸어 제출하였다
다만 제출 코드의 경우 무조건 1 + dp[i - 1] 값을 계산하고 + if 조건에 따라 모든 조건문을 검사하다보니
이 코드가 조금 더 빠른 계산이 될 수도 있을 것 같아 제출해보았더니 역시나 이 코드가 조금 더 빨랐다
elif로 엮었으니 뭐 당연한 결과이기는 하다
시간 차이는 대략 이정도.
dp = [0] * (n + 1)아 그리고 위와 같은 식으로 배열 할당이 가능한 것도 재밌었다
컴파일 시에 알아서 배열 크기만큼 동적할당을 해주는 건가?
