본문 바로가기

algorithm/Dynamic Programming

 (10)
[C++] BOJ 2579 계단 오르기 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 코드 #include #include using namespace std; // 0: 앞계단 안밟음(1연), 1: 앞계단 밟음(2연) int dp[305][2]; int main() { int n; cin >> n; cin >> dp[1][0]; dp[1][1] = dp[1][0]; cin >> dp[2][0]; dp[2][1] = dp[1][0] + dp[2][0]; for (int i = 3; i >..
[C++] BOJ 9095 1, 2, 3 더하기 문제 백준 9095번 Adding 1s, 2s, and 3s https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 코드 #include #include using namespace std; int n, t; int dp[15]; int main() { cin >> t; dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i = 4; i > n; cout
[C++] BOJ 1932 삼각형 문제 백준 1932번 The Triangle https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 #include #include using namespace std; int triangle[501][501], dp[501][501]; int n; int main() { cin >> n; for (int i = 1; i triangle[i][j]; } } dp[1][1] = triangle[1][1]; int ans = 0; for (int i = 1; i
[C++] BOJ 11048 이동하기 문제 백준 11048번 이동하기 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 코드 #include #include using namespace std; int n, m; int maze[1001][1001]; long long dp[1001][1001]; int main() { cin >> n >> m; for (int i = 1; i maze[i][j]; } } dp[1][1] = maze[1][1]; for (int i =..
[C++] BOJ 1010 다리 놓기 문제 백준 1010번 다리놓기 www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 > n >> m; cout
[C++] BOJ 13301 타일 장식물 문제 백준 13301번 타일장식물 www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net 코드 #include using namespace std; long long pibo[85]; int N; int main() { pibo[1] = 1; pibo[2] = 1; cin >> N; for (int i = 3; i
[C++] BOJ 9625 RIJEČI (BABBA) 문제 백준 9625번 BABBA www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 코드 #include using namespace std; int arr[50][2]; //arr[i][0]:number of A, arr[i][1]: number of B int k; int main() { arr[0][0] = 1; arr[0][1] = 0; cin >> k; for (int i = 1; i
[C++] BOJ 10870 피보나치 수 5 문제 백준 10870번 www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 코드 #include using namespace std; int pibo[21]; int n; int main() { pibo[0] = 0; pibo[1] = 1; cin >> n; if (n == 0) cout

티스토리툴바