❗증말 힘들게 푼 문제라는걸 티내기 위해 효율을 포기하고 문제를 공부한 순서대로 적었습니다. 찐 풀이는 [정답] 부분을 누르면 이동됩니다!
.
.
백준 문제를 풀어보던중... 자신만만하게 1단계를 풀었지만....
알고리즘에 대한 지식이 필요한 2단계부터..... 풀수가 없다...
문제를 이해할수도 없어서 우째야 하나 하다가!
우리에겐 chatGPT가 있잖아! 대기업이 만들어준 개인과외슨생림~❤️
[문제] 1463: 1로 만들기
https://www.acmicpc.net/problem/1463
[질문] DP 알고리즘이 뭐야?
해설을 보다가 이 문제를 dp알고리즘으로 푼다는 것을 알았다.
그럼 dp 알고리즘은 뭘까?
DP는 동적 계획법(Dynamic Programming)으로 문제를 더 작은 하위 문제로 나누어 '하나의 문제는 단 한번만 푸는 알고리즘'이라고 한다. 즉, 비효율성을 개선시키는 특징이 있다. 보다시피 이름에 큰 뜻은 없고, 처음 만든 사람이 이름 멋지게지으려고 그렇게 붙였다고 한다더라.ㅎ
gpt로 이해가 안가서 유투브로 수업을 들었다.
[정리] DP 알고리즘의 목적
📍메모리를 사용하여 중복연산을 줄여서 수행속도를 개선한다!
(1) 메모리를 사용하여 = 기존 배열 외에 새로운 배열, 자료구조를 만듦
(2) 중복연산을 줄여서 = 한번 연산한 결과를 그 배열에 담아 다시는 같은 연산을 하지 않도록 함
그렇게 되면 수행속도가 당연히 빨라진다!
그럼 문제는 어떻게 풀까,,?
gpt한테 물어보았다.
(구글링하는게 더 빠르지 않나 하겠지만~~ 맞다. 물론 그게 더 효율적이다. 이미 잘 설명된 블로그들이 많으니까~~ 하지만 아직 남는것이 시간인 젊은이이기 때문에 gpt에게 굳이 물어보았다. 살펴본 블로그들이 다 이해가 안돼서 gpt에게 도망온거다. )
알려준 코드는 아래와 같다. 하나하나 살펴보려고 했는데!
아 개웃겨 아니 집티야 근데 틀렸잔아...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
때려쳐
안되지
추라이! 리츄라이!!!
정답코드는 아래와 같다. 코드를 하나하나보면서도 왜....?싶었는데 내가 이해한 방향이 풀이방향이랑 완전 달랐던 것이다!
내 생각: 입력값 x를 직접 여러 경우의 수로 나눠야겠구나. 그리고 그 경우들의 연산횟수를 배열에 넣고 최솟값을 구해야지!
풀이: 한번씩만계산해 제발~ 누적된 값 좀 써먹어~~
[정답]
X = int(input())
dp = [0] * (X+1)
for i in range(2, X+1):
dp[i] = dp[i-1] + 1
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2]+1)
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
print(dp[X])[풀이]
#DP 알고리즘의 목적
#📍메모리를 사용하여 중복연산을 줄여서 수행속도를 개선한다!
#(1) 메모리를 사용하여 = 기존 배열 외에 새로운 배열, 자료구조를 만듦
#(2) 중복연산을 줄여서 = 한번 연산한 결과를 그 배열에 담아 다시는 같은 연산을 하지 않도록 함
x = int(input())
#1. 목적(1)을 충족시키기 위한 새로운 배열 d 생성
#d = 1이 되기 위한 연산의 최솟값
d = [0]*(x+1)
#2. d[2]부터 d[n+1]까지 도는 for문
#d[0] = 0으로, 1이 1로 되는데 걸리는 최소연산횟수인 0
#d[1] = 1로, 2가 1이 되는데 걸리는 최소연산횟수인 1
for i in range(2, x+1):
#3. d[i] = i가 0이 되는데 걸리는 최소한의 연산횟수
#ex. d[3]이면, 3에서 1을 빼는 연산을 해 2가 되므로, d[3] = d[2]+1
d[i] = d[i-1]+1
if i%2==0:
d[i] = min(d[i],d[i//2]+1)
if i%3==0:
d[i] = min(d[i],d[i//3]+1)
print(d[x])