'📜 코딩테스트/BAEKJOON\다이나믹 프로그래밍' 카테고리의 글 목록 (2 Page)

백준 2579번(DP) : 계단 오르기 (JAVA) 문제 풀이

2021.08.12

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ✏️ 문제 🔐 문제 해결 문제의 조건을 해석해보면 아래와 같습니다. 계단은 한번에 한칸 또는 두칸을 오를 수 있습니다. 연속된 세 개의 계단을 밟아서는 안됩니다. 1 칸씩 세번 연속 오르면 안된다는 뜻! 마지막 칸은 무조건 밟아야 합니다. 1. 테이블 정의하기 dp[i][j]의 i는 i 번째 계단에 올랐을 때의 최대 점수의 합이 되고, j는 현재까지 몇번을 연속해서 계단을 밟고 왔는지를 뜻합니다. 그렇다면, ..

📜 코딩테스트/BAEKJOON\다이나믹 프로그래밍

백준 9095번(DP) : 1, 2, 3 더하기 (JAVA) 문제 풀이

2021.08.10

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ✏️ 문제 🔐 문제 해결 1. 테이블 정의하기 테이블은 dp[i]를 1,2,3으로 표현할 수 있는 횟수로 설정하겠습니다. 2. 점화식 구하기 먼저 dp[4]는 본문에도 나와있듯이 아래와 같이 총 7가지가 있습니다. 이것을 1, 2, 3으로 나눠서 생각해보자면, 하나의 숫자를 3로 고정하고, 나머지 1을 1, 2, 3으로 조합하는 경우 1 + 3 하나의 숫자를 2로 고정하고, 나머지 2를 1, 2, 3으로 조합하는 경우 1 + 1 + 2 2 + 2 하나의 숫자를 1로 고정하고, 나머지 3을 1, ..

📜 코딩테스트/BAEKJOON\다이나믹 프로그래밍

백준 1463번(DP) : 1로 만들기 (JAVA) 문제 풀이

2021.08.10

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ✏️ 문제 🔐 문제 해결 다이나믹 프로그래밍은 아래 세가지 순서를 따라서 문제를 풀이합니다. 테이블 정의하기 점화식 찾기 초기값 설정 1. 테이블 정의하기 테이블의 값은 당연히 i의 최소 연산 횟수가 되겠습니다. 2. 점화식 찾기 i를 계산하는 방법은 총 3가지가 있습니다. 2로 나눈 나머지가 0일 경우, 2로 나눈다. 3으로 나눈 나머지가 0일 경우, 3으로 나눈다. 1을 뺀다. i의 최소 연산 횟수를 저장하는 배열을 dp라고 정의할 때, dp[i]의 값은 아래와 같습니다. dp[i] = Math.min(dp..

백준 2579번(DP) : 계단 오르기 (JAVA) 문제 풀이

백준 9095번(DP) : 1, 2, 3 더하기 (JAVA) 문제 풀이

백준 1463번(DP) : 1로 만들기 (JAVA) 문제 풀이

티스토리툴바