Algorithm/Dynamic Programming

[백준 2579번] 계단 오르기 (C++)

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단 오르기 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 다이나믹 프로그래밍은 테이블 정의, 점화식 작성, 초기값 정하기으로 구분할 수 있습니다. 테이블 정의 d[n][i]은 n번째 계단까지의 최대 점수를 의미합니다. (i는 마지막에 연속된 계단의 개수) 연속된 세 개의 계단을 밟지 않아야 된다는 조건이 있기 때문에 2차원 배열로 구성하였습니다. 점화식 작성 d[n][1]은 연속된 계단의 개수가..

[백준 9095번] 1, 2, 3 더하기 (C/C++)

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 1, 2, 3 더하기 문제는 백트래킹 또는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. th번째에서 1, 2, 3 중에 선택하고, th + 1번째를 선택하도록 하면 됩니다. 아래는 백트래킹을 이용한 코드입니다. #include using namespace std; int selected[11]; int n, m, ans = 0; void back(int th){ int s = 0; for(int i = 0; i < th - 1; i++) s += selected[i]; // 현재까지 선택..

[백준 1463번] 1로 만들기 (C/C++)

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1로 만들기 문제는 BFS 또는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. ⚠️ 주의! N의 최대 값인 10의 6승도 방문 표시 할 수 있도록 방문 표시 배열의 크기를 충분히 주어야 합니다. 아래는 BFS를 이용한 코드입니다. #include using namespace std; int vis[1000001]; void bfs(int n){ queue q; q.push(n); vis[n] = 1; while(!q.empty()){ int cur = q.front(); q.pop(); if(cur < 1..