https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
나만 어려운 문제일 수 있다 ㅎㅎ
피보나치문제는 되게 간단하던데 이 문제는 답지를 봐도 이해가 안되어서 하나하나 적으면서 풀어봤다.
이해가 안갔던 이유:
계산한 값들을 배열에 저장해야된다고 생각했다.
숫자가 인덱스라는 점이 안 와 닿았다.
코드 보면서 얘기해보자~~
먼저 dp 다이나믹 프로그래밍은
반복적인 계산을 효율적으로 처리를 하는 알고리즘이다.
큰문제를 작은 문제로 나누어 해결하고 그 결과를 저장해놨다가 재사용하여 중복계산을 피한다.
피보나치 보면 이해가 바로 가능하다
https://www.acmicpc.net/problem/2748
n = int(input())
#앞서 계산된 결과를 저장하기 위한 DP테이블 초기화
#n번째
d = [0]* (n+1)
print("d:",d)
#피보나치 수 : 0, 1, 1, 2, 3, 5....
#0,1로 시작하는 값
#인덱스 1번째 1
d[1] =1
#반복문은 2번째부터 시작.
for i in range(2, n+1): #2~n까지
#1= 1+0
d[i] = d[i-1]+ d[i-2]
print(d[n])
처음 0,1을 주고 시작함!
그러면 인덱스 2, 부터 계산됨
그렇다면 이 문제.
피보나치는 더한 값들을 배열 d에 기록해서 간단했는데
이문제는 구하고자 하는 값이 횟수이다. 횟수를 기록해야한다.
숫자 10이 몇 번의 횟수를 거쳐 1이 되었냐~ 는 문제이다.
이 숫자 10과 횟수의 관계를 코드로 정립 못했었다..
횟수를 기록한 d배열의 인덱스가 "주어진 숫자" 역할을 했다. 그게 잘 안와닿았다.
즉 인덱스 3은 숫자 3. 그러면 인덱스 3에 횟수를 기록하게 되는 것이다.
횟수를 기준으로 하니, 현재 횟수가 이전횟수 + 1이다라는게 겨우 이해되었다.
숫자가 2나 3으로 나눠지는 경우 : 예) 숫자가 6이면 "이전5의 횟수+ 1"을 하면 4가 되는데, 숫자 6은 2로 나눠지기때문에
최솟값으로 비교를 한다. "이전5의 횟수+ 1" 과 "d[6//3] 즉 d[2] 숫자2의 횟수에 1을 더한 값"을 비교하는 것이다.
나는 하나하나 값 넣어서 적어보면서 이해했다 ㅎㅎㅎ
# 답지
# n = int(input())
n = 10
print('n',n)
#계산한 횟수를 저장하는 용이래!!!
d = [0] * (n+1)
print("d",d)
for i in range(2, n+1): #2부터하는이유는0,1은 나누어떨어지지 않아서 횟수가 걍 0이라서!
d[i] = d[i-1] +1 #더하기 1을 하는 이유는 기존횟수느 = 이전 횟수에 + 1 식 늘어나니까.
#i가 3으로 나눠지는 값이면
if i %3 == 0:
#숫자 3의 횟수는 = 이전 횟수에 하나더한 횟수거나, 3으로 나눈 값의 횟수에 하나 더한 횟수! 둘중에 더 작은 값!
d[i] = min(d[i], d[i//3]+1)
print("3d[i]:", d[i])
if i%2 == 0:
d[i] = min(d[i], d[i//2]+1)
print(d[n])
'코딩테스트 > 백준' 카테고리의 다른 글
| 마방진 forming a magic square (0) | 2023.06.19 |
|---|---|
| 백준 1920번 이진탐색으로 (0) | 2023.06.15 |
| 정렬 (0) | 2023.05.30 |
| 그래프와 DFS(재귀함수, 스택으로 구현)와 BFS(큐로 구현) - 파이썬 코드 (2) | 2023.05.26 |
| for문과 while차이점 (0) | 2023.05.15 |
