Optional

[문제] https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net [풀이] 다이나믹 프로그래밍(DP), Prefix Sum [코드] #include using namespace std; int n,m; int a[100004], d[100004]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; d[0] = 0; for(int i=1; i> a[i]; d[i] =..

[문제] https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net [풀이] 다이나믹 프로그래밍(DP) [코드] #include using namespace std; int d[10005]; int mod = 10007; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; d[1] = 1; d[2] = 2; for(int i=3; i

[문제] https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net [풀이] 다이나믹 프로그래밍(DP) [코드] #include using namespace std; int d[1005][3]; int r[1005], g[1005], b[1005]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=1; i> r[i] >> g[i] >> b[i];..

[문제] https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net [풀이] 정렬 [코드] #include using namespace std; int n; long long a[100005]; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0; i> a[i]; sort(a, a+n); int cnt = 0; long long mxval= -(111

[문제] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net [풀이] 다이나믹 프로그래밍 [코드] #include using namespace std; int d[20]; int main() { ios::sync_with_stdio(0); cin.tie(0); d[1] = 1; d[2] = 2; d[3] = 4; for(int i=4; i> t; while(t--){ int n; cin >> n; cout

[문제] https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net [풀이] 다이나믹 프로그래밍 [코드] #include using namespace std; int s[305]; int n; int d[305][3]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=1; i> s[i]; if(n==1){ cout