본문 바로가기

DP3

[ 백준 - 2579 ] 계단 오르기 난이도 : S3Link : https://www.acmicpc.net/problem/2579Tag : DP 문제 탐색하기 - 마지막 계단까지 도착했을때 얻을 수 있는 최댓값을 구하여야한다.- 계단은 한번에 한계단, 두계단씩 오를 수 있다.- 세개의 계단은 모두 밟아서는 안된다.시도 1 ( 실패 😓)떠오른 문제 해결 방법먼저 테이블은 D[i] = 해당 계단까지 도착했을 때의 최댓값 으로 정의하였습니다.식은 k = stairs[i-1], stairs[i-2] 중 더 큰값인 계단의 인덱스. D[i] = D[k] + stairs[i] 입니다. 이유는 i번째의 계단을 오르기 위해서는 연속해서 3계단을 오를 수 없기 때문에 i-1, i-1계단중 하나를 선택해야합니다. 두계단을 모두 선택한다면 i번째 계단을 오를.. 2025. 5. 10.
[ 백준 - 9095 ] 1, 2, 3 더하기 난이도 : S3Link : https://www.acmicpc.net/problem/9095Tag : DP 문제 탐색하기 - 정수 n이 주어졌을때 n을 1,2,3의 합으로 나타내는 경우의 수를 구하여라시도 1 ( 실패 😓)떠오른 문제 해결 방법DP는 점화식이 떠오르지 않으면 풀기가 어려운것 같습니다.계속해서 생각해봤지만 점화식을 찾지 못하여 힌트를 보았습니다. 시도 2 ( 성공 😲)떠오른 문제 해결 방법힌트는 다음과 같았습니다.4 = ?1+1+1+1, 3+1, 2+1+1, 1+2+11+1+2, 2+21+3 보이시나요? 맨 뒷자리를 제외한 숫자를 보면서 점화식을 찾았습니다. 바로 맨뒤에 1로 고정한다면 3의 경우의수와 같고, 동일하게 2로 고정한다면, 2의 경우의수와 같고, 마지막 3으로 고정한다면 .. 2025. 5. 8.
[ 백준 - 1463 ] 1로 만들기 난이도 : S3Link : https://www.acmicpc.net/problem/1463Tag : DP 문제 탐색하기 - 특정 숫자를 1로 만드는 가장 적은 횟수를 출력한다.- 3으로 나누기, 2로 나누기, 1빼기가 가능하다.1빼기가 있기 때문에 무조건 1로 만들기가 가능하다. 시도 1 ( 성공😲)떠오른 문제 해결 방법 DP문제는 점화식을 만드는게 중요하기 때문에 일단 난이도가 쉬운 문제를 접근하였습니다.DP에서는 배열을 잡는 것이 중요합니다.이번 문제에서는 배열을 count[i]=1로만드는 가장 적은 횟수로 하였습니다.그렇게 되면 다음과 같은 관계를 나타낼수 있습니다.count[1] = 0 //이미 1count[2] = 1 //...count[i]=min( count[i/3]+1, count[.. 2025. 5. 7.

티스토리툴바