+++ author = “jyukki” categories = [“백준”] tags = [“algorithm”, “C++”, “DP”] date = “2017-11-29” description = “algorithm” featured = "" featuredalt = "" featuredpath = “date” linktitle = "" title = “[백준]2579 계단 오르기” +++ https://www.acmicpc.net/problem/2579 풀이: b[i][0] 은 i번째를 골랐을 때, i-1번째를 안고른 경우의 수 b[i][1] 은 i번째를 골랐을 때, i-1번째를 고른 경우의 수 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <iostream>#include <algorithm>using namespace std; int main(void) { int n; cin >> n; int a[301]; for (int i = 0; i < n; i++) { cin >> a[i]; } int b[301][2] = { a[0],0,a[1],a[0] + a[1],0 }; for (int i = 2; i < n; i++) { for (int t = 0; t < 2; t++) { if (t == 0) b[i][t] = max(b[i - 2][0], b[i - 2][1]) + a[i]; if (t == 1) b[i][t] = b[i - 1][0] + a[i]; } } cout << max(b[n - 1][0], b[n - 1][1]) << endl; return 0; }

https://www.acmicpc.net/problem/2616 풀이: a[i][t] : i 번째 까지의 소형 기관차 들이 t번째 객차까지 끌 수 있는 최대 승객의 수 첫 번째 소형기관차부터 앞으로 m칸만큼 객차칸수를 증가시켜가며 최댓값을 구한다. 만약 앞에 값이 더 크다면 앞에값을 선택한다. 객차의 칸이 겹칠 수 없으므로 이번 소형기관차(a[i][t])보다 m보다 작은 객차수를 가지고 있는 이전의 소형기관차(a[i - 1][t - m])를 이번 소형기관창의 t번째 최대 승객 수에 더해준다. a[i][t] = max(a[i][t - 1], sum[t] - sum[t - m] + a[i - 1][t - m]; 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream> #include <algorithm> using namespace std; int n, m, sum[50002] = { 0 }, a[4][50002] = { 0 }; int main(void) { cin >> n; for (int i = 1; i <= n; i++) { cin >> sum[i]; sum[i] += sum[i - 1]; } cin >> m; for (int i = 1; i <= 3; i++) { for (int t = i * m; t <= n; t++) { a[i][t] = max(a[i][t - 1], sum[t] - sum[t - m] + a[i - 1][t - m]); } } cout << a[3][n] << endl; return 0; } 시간 초과 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <iostream> #include <algorithm> using namespace std; int a[50001]; int main(void) { int n, m; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } cin >> m; int num = 0; for (int i = 0; i <= n - 3 * m; i++) { for (int t = i + m; t <= n - 2 * m; t++) { for (int y = t + m; y <= n - m; y++) { int cnt = 0; for (int q = 0; q < m; q++) { cnt += a[i + q] + a[t + q] + a[y + q]; } num = max(num, cnt); } } } cout << num << endl; return 0; } 메모리 초과 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <iostream> #include <algorithm> using namespace std; int n, m; int sum[50002] = { 0 }; int small(int a,int b,int c) { if (a + 3 * m > n) return 0; if (b + 2 * m > n) return small(a + 1, a + m + 1, a + 2 * m + 1); if (c + m > n) return small(a, b + 1, b + m + 1); int num = 0; num += sum[a + m] - sum[a] + sum[b + m] - sum[b] + sum[c + m] - sum[c]; return num = max(num, small(a, b, c + 1)); } int main(void) { cin >> n; for (int i = 1; i <= n; i++) { cin >> sum[i]; sum[i] += sum[i - 1]; } cin >> m; cout << small(0, m, 2 * m) << endl; return 0; }

https://www.acmicpc.net/problem/2688 풀이: a[t][y] : t + 1 개의 자릿수에서의 줄어들지 않는 수의 갯수 a[t][y] = a[t][y - 1] + a[t - 1][y] 앞자리의 갯수가 1 증가할 때 마다 이전 자릿수의 개수를 더해가는 방식으로 구한다. 최종 자릿수 9가되면 모든 수가 누적되어 있으므로 출력한다. 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream> using namespace std; long long a[65][10] = { 1,2,3,4,5,6,7,8,9,10,0 }; int main(void) { int T, n; cin >> T; for (int i = 0; i < T; i++) { cin >> n; for (int t = 1; t < n; t++) { a[t][0] = 1; for (int y = 1; y < 10; y++) { a[t][y] = a[t][y - 1] + a[t - 1][y]; } } cout << a[n - 1][9] << endl; } return 0; } 사간 초과 풀이: 처음 풀이를 할 때 저번 1038 감소하는 수를 푸는 것처럼 하나하나 만들어 가면서 카운트를 하려 했으나 시간초과가 난다.

https://www.acmicpc.net/problem/2743 풀이: 단어의 길이를 출력 코드: 1 2 3 4 5 6 7 8 #include <iostream> #include <string> using namespace std; int main(void) { string a; cin >> a; cout << a.length() << endl; }

https://www.acmicpc.net/problem/2749 풀이: 코드 설명은 피보나치 코드 참고 참고의 문제와는 다르게 매우 큰 수가 들어온다. 피보나치를 n으로 나누면 주기가 생성되는데 주기로 끊어서 풀도록 한다. 코드: 1 2 3 4 5 6 7 8 9 #include <iostream> using namespace std; long long a[3] = { 0,1 }, n; int main() { cin >> n; for (int i = 2; i <= n % 1500000; i++) a[i % 3] = (a[(i - 1) % 3] + a[(i - 2) % 3]) % 1000000; cout << a[(n % 1500000) % 3] << endl; } 참고: https://www.

https://www.acmicpc.net/problem/2858 풀이: 전체 사각형의 면적으로 가로 세로를 찾은 후 그 가로 세로에서 2를 뺀것의 넓이가 안쪽 갈색의 면적과 같다면 그 가로 세로가 각각 L, W 라고 할 수 있다. 코드: 사용언어 : Python 3 1 2 3 4 5 r,b=map(int,input().split()) for i in range(3,(r+b)//2): if((r+b)%i==0 and (i-2)*(((r+b)/i)-2)==b): print(((r+b)//i),i) break