반응형
백준 1453번 1로 만들기
DP
[문제]
기본적인 DP(동적계획법) 문제
오랜만에 풀게되서 dp를 생각하지 못했고 dp개념을 다시 공부한 후 풀었다.
핵심은 1,2,3번으로 나온 연산의 최소횟수를 구하는 것
[과정]
dp - BottomUp 풀이 / for문 사용
다른 하나는 재귀를 사용하는 TopDown 풀이가 있는데 이 문제에서는 BottomUp풀이를 사용했다.
- n에 변수 입력받기
- dp배열을 0이 (x+1)개 있는 리스트로 초기화
- dp[1]은 0이고 1이 1로 되는데 필요한 연산은 0회라는 뜻
- 즉, 이후에 dp[2]는 2가 1이 되는데 필요한 최소 연산 횟수인 1이 될 것
- 2부터 n+1까지 반복
- dp[i]=dp[i-1]+1 : d[i]는 숫자 i가 1이 되는데 걸리는 최소한의 연산 횟수를 저장
- i에서 1을 빼면 i-1이 되므로, dp[i-1]+1을 함으로써, dp[i-1] (i-1이 1이 되는데 필요한 최소한의 연산) + 1 (i에서 1을 빼서 i-1이 되는데 필요한 연산 횟수 1회)로 초기화
- if i%2==0: dp[i]=min(dp[i],dp[i//2]+1) : i가 2로 나누어 떨어질 때, dp[i]와 dp[i//2]+1중 최솟값을 dp[i]에 저장
- dp[i//2]+1 : i를 2로 나눈 값이 1이 되는데 걸리는 최소 연산 횟수+i를 2로나누는 연산횟수 1회
- if i%3==0: dp[i]=min(dp[i],dp[i//3]+1) : i가 3으로 나누어 떨어질 때, dp[i]와 dp[i//3]+1 중 최솟값을 dp[i]에 저장
[소스코드]
# 백준 1453 1로만들기
n = int(input())
dp = [0]*(n+1)
for i in range(2, n+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[n])
직관적으로 dp배열의 변화를 보고싶어서 출력문을 찍어본 형태는 다음과 같다.
[통과]
// 스터디에서 dp문제가 나와 dp개념을 다시 잡기위해서 dp기본문제를 풀어봤다.
반응형
'코딩테스트 문제풀이 > beakjoon' 카테고리의 다른 글
[백준] 9251 LCS (0) | 2022.08.22 |
---|---|
[백준] 7795 먹을 것인가 먹힐 것인가 (0) | 2022.08.19 |
[백준] 2910 빈도 정렬 (0) | 2022.08.18 |
[백준] 5430 AC (0) | 2022.08.12 |
[백준] 1021 회전하는 큐 (0) | 2022.08.12 |
댓글