본문 바로가기

백준/동적프로그래밍51

백준 9507 c++ "Generations of Tribbles" -PlusUltraCode- https://www.acmicpc.net/problem/9507 [필자 사고]동적 프로그래밍 문제이다.동적 프로그래밍에서 가장 중요한 점은 점화식을 세우냐 못 세우냐에 따라 풀수 있는지 없는지 갈린다.이 문제는 점화식 자체를 공유했다. 점화식 대로 문제를 풀게 되면 쉽게 풀리게 된다. [코드 해설]3. 입력 처리 및 실행 흐름 (Game_Start 함수)Game_Start() 함수는 프로그램의 핵심 실행 흐름을 담당합니다.사용자로부터 정수 NNN을 입력받습니다. NNN은 테스트 케이스의 개수를 나타냅니다.dpdpdp 벡터를 크기 68로 설정하고 초기화합니다.Make_Koong()을 호출하여 Koong 수열을 미리 계산합니다.이렇게 함으로써 같은 값을 반복해서 계산하는 비효율성을 제거하고, 미리 계산된 .. 2025. 2. 9.
백준 14916 c++ "거스름돈" -PlusUltraCode- https://www.acmicpc.net/problem/14916  [필자 사고] 동적 프로그래밍 문제이다.여기서 집중해서 봐야 될 부분은 2와 5이다.dp라는 것의 idx가 의미하는 것은 현재 문제에서 주어지는 최선의 값을 도출하는 값이다.즉 모든 dp가 최선의 값을 도출해야 된다는 점이다. 즉 필자는 아래와 같은 점화식을 만들었다.dp[i] = min(dp[i-2],dp[i-5])+1;  나머지 부분은 예외처리를 하면 쉽게 풀 수있다.[코드 해설]1. 게임 시작 (Game_Start 함수)Game_Start 함수는 게임을 시작하는 역할을 하며, 특정 규칙을 기반으로 dp 배열을 사용하여 최적의 해를 구하는 동적 계획법(DP) 알고리즘을 구현한다.2. 입력 처리사용자로부터 정수 N을 입력받으며, 이를.. 2025. 2. 7.
백준 9655 c++ "돌 게임" -PlusUltraCode- https://www.acmicpc.net/problem/9655 [필자 사고]홀 수 짝수 개념으로 해도 문제는 풀린다.다만 DP공부중이기 때문에 dp적 사고로 풀어야 겠다.문제에서 주어진 조건은 1과 3 즉 점화식을 구해보면 현재 DP = 과거(DP1) 과 과거(DP3) +1 을 해서 flag 형태로 풀게되면 문제는 풀린다.[코드 해설]1. 문제 개요이 문제는 돌을 1개 또는 3개 가져갈 수 있는 돌 게임에서 마지막 돌을 가져가는 사람이 승리하는 게임입니다.상근(SK)과 창영(CY)이 번갈아 가며 돌을 가져갑니다.N개의 돌이 있을 때, 누가 이기는지를 출력하는 문제입니다.2. 입력 처리 및 초기 조건N을 입력받습니다.dp 배열을 선언하여, dp[i]는 i개의 돌이 있을 때 최소 턴 수를 저장합니다.초기.. 2025. 2. 6.
백준 9465 c++ "스티커" -PlusUltraCode- https://www.acmicpc.net/problem/9465  [필자 사고]동적 프로그래밍 문제이다.필자는 해당 dp점화식을 다음과 같이 설계했다.dp[i][k] = buf[i][k] + 이전 dp값들즉 현재 위치는 반드시 값이 들어가야 되고 이전 dp의 최대값들을 갱신하는 형태로 설계를 했따.[코드 해설]2. 입력 처리 (Init 함수)Init() 함수는 입력을 받아서 점수 배열과 DP 배열을 초기화하는 역할을 합니다.buf (입력된 점수 저장)와 dp (최대 점수 저장) 벡터를 초기화합니다.buf는 두 개의 행과 N개의 열을 가지므로, buf[0]과 buf[1]에 점수를 저장합니다.dp 배열을 이용하여 초기 조건을 설정합니다.첫 번째 열(dp[0][0], dp[1][0])은 buf[0][0], .. 2025. 2. 6.

티스토리툴바