https://www.acmicpc.net/problem/1660 풀이: b[i] : i개의 대포알의 개수로 만들 수 있는 사면체의 최소 개수 a[i] : 사면체의 사이즈가 i인 대포알의 개수 b[i] = min(b[i], b[num - a[i]] + 1) 주의사항: 시간초과에 유의하여 메모이제이션을 하도록한다. min함수를 사용하므로 초기값을 매우 크게 잡아주는 것을 잊지말자. 코드: 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 27 #include <iostream> #include <algorithm> using namespace std; int a[200] = { 0 }, b[300010] = { 0 }, q = 1; int cap(int num) { if (num <= 0 ) return 0; if (b[num]) return b[num]; b[num] = 300000; for (int i = q; i > 0; i--) { if (a[i] <= num) b[num] = min(b[num], cap(num - a[i]) + 1); } return b[num]; } int main(void) { int n, cnt = 1; cin >> n; while(true) { a[q] = a[q - 1] + cnt; cnt += q + 1; if (a[q] > n) break; q++; } cout << cap(n) << endl; return 0; }

https://www.acmicpc.net/problem/1668 풀이: 왼쪽에서부터 높이를 세며, 더 높은 트로피가 나올때마다 카운트를 증가 오른쪽도 똑같이 한 후 카운트를 출력 코드: 사용언어 : Python 3 1 2 3 4 5 6 7 8 9 10 11 12 13 n,cnt1,cnt2,k1,k2=int(input()),0,0,0,0 h={} for i in range(n): h[i]=int(input()) for i in range(0,n): if(h[i]>k1): k1=h[i] cnt1+=1 if(h[n-1-i]>k2): k2=h[n-1-i] cnt2+=1 print(cnt1) print(cnt2)

https://www.acmicpc.net/problem/1720 풀이: a[i] : 2Xi인 타일을 채울 수 있는 경우의 수(중복 포함) b[i] : 2Xi인 타일을 채울 수 있는 경우의 수(중복 미포함) 짝수 일때와 홀수일때 대칭의 경우의 수가 다르므로 나눠서 계산한다. 코드: 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 27 #include <iostream> using namespace std; int a[32] = { 1,1,3 }; int b[32] = { 1,1,3 }; int main(void) { int n; cin >> n; for (int i = 3; i <= n; i++) { a[i] = a[i - 1] + a[i - 2] * 2; b[i] = a[i]; } int t = 0; if (n % 2 == 1) { while (n - t >= 2 && t < n / 2 + 1) { b[n] -= a[n - t - 2]; t++; } } else { while (n - t >= 2 && t + 1 < n / 2) { b[n] -= a[n - t - 2]; t++; } } cout << b[n] << endl; return 0; }

https://www.acmicpc.net/problem/1789 풀이: 입력받은 숫자를 N 이라고 할 때 (-1 + (1+8*N)^0.5)/2 에 소수점을 버린 값이 최대 개수이다. n(n+1)/2 >= k n^2+n-2k >= 0 n의 최솟값이다. 코드: 사용언어 : Python 3 1 print(int((-1+(1+8*int(input()))**.5)/2))

https://www.acmicpc.net/problem/1834 풀이: 나머지와 몫이 같은 수는 N+1에 배수의 형태로 나타난다. 3일때 4,8 , 4일때 5,10,15 등 n+1의 배수가 n-1번 나타난다. 즉 (n+1)Σ(n-1) 이다. (n+1)n(n-1)/2 (n^3-n)/2 코드: 사용언어 : Python 3 1 2 n=int(input()) print((n**3-n)//2)

https://www.acmicpc.net/problem/1940 풀이: 재료들이 가진 고유의 번호를 가진 리스트를 a라고 하자 이 때 갑옷을 만드는데 필요한 숫자인 M에서 i번째 고유번호인 a[i]를 뺀 값이 리스트 a에 있다면 갑옷을 1개 만들 수 있는 것이므로 카운트를 1 증가시킨다. 계속 증가시키다 보면 서로 짝이되는 수 2개를 모두 카운트를 시키게 되므로 2로 나눠준다. 코드: 사용언어 : Python 3 1 2 3 n,m=int(input()),int(input()) a=input().split() print(sum(a.count(str(m-int(a[i])))for i in range(n))//2)