-
[BOJ] 10759: 팰린드롬 경로3
10759: 팰린드롬 경로3 풀이 d[i][j] = 문자열의 길이가 k이고, i행에서 시작해서 j행으로 끝나고, 그 문자열의 중심이 배열의 대각선(왼쪽 아래~오른쪽 위)에 있을 때, 그 문자열이 팰린드롬인 경우의 수 d[k][i][j] = d[k-2][i][j]+d[k-2][i+1][j]+d[k-2][i][j-1]+d[k-2][i+1][j-1] 식은 위와 같고, 배열은 k를 토글링 해서 n^2개만 사용할 것이다. (1,1)~(n,n)의 문자열은 길이가 항상 홀수이다. 중앙의 diagonal 대각선을 기준으로, 팰린드롬의 길이를 앞뒤로 2씩 확장해 나갈 수 있다. (a,b)~(c,d)의 중심이 대각선에 겹치려면, (a-1)+(b-1) = |(c-n)+(b-n)|을 만족해야 한다. (두 점이 각 끝점으로부터 떨어진 거리가 같아야 한다.) a와...
-
[BOJ] 2294 : 동전 2
2294 : 동전 2 풀이 가져가 지독한 그리움 기억 속 널 다시 데러가 난 아무렇지 않은 척 애를 써도 또다시 울컥하고 말아 아직도 난 코드 #include <cstdio> int n, k, t, d[100001]; int main() { scanf("%d %d", &n, &k); for (int i = 1; i <= k; i++) { d[i] = 1e9; } for (int i = 1; i <= n; i++) { scanf("%d", &t); for (int j = t; j <= k; j++) {...
-
[BOJ] 2133 : 타일 채우기
2133 : 타일 채우기 풀이 둠두둠칫 코드 #include <cstdio> int main() { int n, d[31] = { 1,0,3 }; scanf("%d", &n); for (int i = 4; i <= n; i += 2) { d[i] = d[i - 2] * 3; for (int j = 4; j <= i; j += 2) d[i] += d[i - j] * 2; } printf("%d", d[n]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++,...
-
[BOJ] 1149 : RGB거리
1149 : RGB거리 풀이 d[i][0] = max(d[i-1][1], d[i-1][2]) d[i][1] = max(d[i-1][0], d[i-1][2]) d[i][2] = max(d[i-1][0], d[i-1][1]) 코드 #include <bits/stdc++.h> using namespace std; int N, r, g, b, R, G, B; int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d %d %d", &r, &g, &b); r += min(G, B); g += min(R, B); b += min(R, G); R = r; G = g; B = b; } printf("%d", min(min(R,...
-
[BOJ] 2156 : 포도주 시식
2156 : 포도주 시식 풀이 . 코드 int max(int a, int b) { return a > b ? a : b; } n, a, b, c, A, B, C, w; main() { for (scanf("%d", &n); n--;) { scanf("%d", &w); C = c, B = b, A = a; c = B + w; b = A + w; a = max(max(A, B), C); } printf("%d", max(max(a, b), c)); } 아무말 백준, 백준 온라인 저지, BOJ,...
-
[BOJ] 2618 : 경찰차
2618 : 경찰차 풀이 dp[i][j] = 경찰차1이 i번째 사건, 경찰차2가 j번째 사건의 위치에 있을 때 거리 합의 최소값 일반성을 잃지 않고, max(i, j)까지의 사건들을 모두 처리했다고 하자. 지금 처리할 사건을 k번째라고 하자. (k = max(i,j)+1) dst(i, j)는 i번째 사건과 j번째 사건 사이의 거리를 구하는 함수라고 하자. 경찰차1이 k번째 사건을 처리하려면, dp[k][j] = dp[k-1][j] + dst(k, k-1) 경찰차2가 k번째 사건을 처리하려면, dp[i][k] = dp[i][k-1] + dst(k, k-1) 점화식을 잘 정의했다면 여기까지 어렵지 않게 떠올릴 수 있다....
-
[BOJ] 1344 : 축구
1344 : 축구 풀이 각각의 팀이 골을 넣고 말고 하는 경우의 수는 총 4가지 모두 계산해 주자 코드 #include <cstdio> int p[12] = { 0,1,4,6,8,9,10,12,14,15,16,18 }; double a, b, d[19][19][19]; int main() { scanf("%lf %lf", &a, &b); a /= 100, b /= 100; d[0][0][0] = 1; for (int t = 0; t <= 17; t++) { for (int x = 0; x <= t; x++) { for (int y = 0; y <= t; y++)...
-
[BOJ] 2688 : 줄어들지 않아
2688 : 줄어들지 않아 풀이 보이지 않아~~ 코드 #include <cstdio> int tc, n; long long sum, d[66][10]; int main() { for (int i = 0; i <= 9; i++) { d[1][i] = 1; } for (int i = 2; i <= 64; i++) { for (int j = 0; j <= 9; j++) { for (int k = 0; k <= j; k++) { d[i][j] += d[i-1][k]; } } } for (scanf("%d", &tc); tc--;) {...
-
[BOJ] 15770 : QueryreuQ
15770 : QueryreuQ 풀이 문자열의 끝 문자가 추가 되거나 삭제 될 때, 매번의 추가/삭제 이후에 모든 부분 팰린드롬의 개수를 빠르게 구해야 한다. 문자가 추가/삭제 된다는 조건과 쿼리 문제라는 생각에 뭔가 어려워 보인다. 문자가 끝에서만 추가되고 삭제되기 때문에, 그냥 fix된 문자열에서 다이나믹으로 팰린드롬 구하는 O(n^2) 알고리즘을 그대로 가져오면 된다. 시간 제한이 1초여서 조금 빡빡한 듯 하지만, 엄밀히 따져보면 10000^2에 나누기 상수가 붙어서 1초 보다 좀 덜 돈다. (그리고 컴파일러 -o2 최적화가 붙으면 간단한 10000^2정도는 1초에 충분히...
-
[BOJ] 1023 : 괄호 문자열
1023 : 괄호 문자열 풀이 sgc109님 풀이 보고 구현했어요 괄호 문자열의 개수를 구하는 점화식을 구하고 (1)에서 괄호 ㄴㄴ 문자열의 개수를 구하는 점화식을 구하고 (2)를 역추적 하면 풀 수 있어요 코드 #include <cstdio> #include <cstring> typedef long long ll; const ll inf = 0x3f3f3f3f3f3f3f3f; int n; ll k, dp[55][105][2]; ll go(int now, int sum, int isWrong) { if (now == n) { return isWrong || sum!=50; } ll &ret = dp[now][sum][isWrong]; if (ret != inf) {...
-
[BOJ] 2453 : 부서 배치
2453 : 부서 배치 풀이 어떤 두 사람의 친하고 친하지 않고를 나타내는 관계가 있다. 관계는 항상 그래프로 표현할 수 있다. 이 문제에서 주어진 관계들을 그래프로 표현하면, 이 관계들이 여러 개의 Connected Component로 나눠질 수 있다. 부서는 반드시 2개가 존재하니까, 컴포넌트마다 그룹1에 들어가는 사람 수와 그룹2에 들어가는 사람 수를 정할 수 있다. 이를 정하는 과정에서 모순이 발생하면 -1을 출력하고 종료해주면 된다. 여기까지 각 컴포넌트마다 두 그룹에 할당되는 인원 수를 정했다. 이제 한 그룹의 사람들을 부서1에 배치할지,...
-
[BOJ] 3114 : 사과와 바나나
3114 : 사과와 바나나 풀이 A는 prefix 누적합, B는 suffix 누적합을 구해주자. 불도저가 [i][j]로 오는 방법은 [i-1][j-1], [i-1][j], [i][j-1] 이 세 가지가 있다. 모든 i, j를 돌면서, 위의 세 가지 경우에 대해 최댓값을 계산해주자. i=1이거나 j=1인 경우의 예외 케이스에 주의하자. 코드 #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; int n, m, i, j, a[1502][1502], b[1502][1502], d[1502][1502]; char s[9]; int main() { scanf("%d %d", &n, &m); for (i = 1; i <= n; i++)...
-
[BOJ] 8098 : Lecture Halls Reservation
8098 : Lecture Halls Reservation 풀이 회의실 배정이랑 비슷하게 생겼다. 오… 이거 데이터 생겨먹은 게 끝나는 시간을 기준으로 정렬해주고 싶게 생겼다. 시간의 최대 범위가 3만이므로, 각각의 시간에 대해, 해당 시간까지의 최대 해를 계산해줄 수 있다. 약간 다이나믹스러운 느낌으로 d[time] = max(d[time], d[start]+end-start) 주어진 구간의 양 끝점만 보고 삭 긁어주면 된다. 시간 범위가 3만보다 (엄청) 크다면 세그트리 등등을 이용해서 풀어줄 수 있겠다. 코드 #include <cstdio> #include <algorithm> using namespace std; int n, r, d[30003]; pair<int, int>...
-
[BOJ] 8095 : The Number of N-k-special Sets
8095 : The Number of N-k-special Sets 풀이 1부터 N까지의 정수를 최대 한 번씩 사용하는데, 인접한 숫자를 사용하지 않고, k이상의 정수를 만드는 경우의 수를 구해야한다. 딱 문제가 저는 다이나믹이에요!!!! 라고 소리지르고 있다. 나는 두 가지 방법으로 풀었다. 아 그리고 답이 long long 범위마저 넘어가므로 Big Integer스러운 어떤 방법이나 언어를 잘 골라서 구현해야 한다. 방법1 dp[i][k] = 1~i를 사용해서 k를 만드는 경우의 수 i-1(인접하면 안 되니까 i-1)보다 작은 j들에 대해, dp[j][k-i]를 누적하여 세어주면 어렵지 않게 계산할...
-
[BOJ] 4243 : 보안 업체
4243 : 보안 업체 풀이 내가 지금 [left, right] 구간을 방문한 상태라고 하면, 다음 상태는 [left-1, right] 또는 [left, right+1]가 될 것이다. 이를 토대로 다이나믹 프로그래밍을 해주자. 단, 다음 두 상태로 나아갈 때 left에 서있는지 right에 서있는지에 따라 거리합이 달라지므로 이를 유의해서 코드를 짜보자. 코드 #include <cstdio> #include <cstring> typedef long long ll; int tc, n, s, a[102]; ll dp[2][102][102]; ll min(ll a, ll b) { return a<b?a:b; } ll dst(int x, int y) {...
-
[BOJ] 15264 : Gambling Guide
15264 : Gambling Guide 풀이 1에서 N으로 가는 기댓값을 구해야 하는데 기댓값을 구할 수가 없다! 그러니까 N에서부터 1로, 거꾸로 가면서 구해주자. 코드 #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; const int n_ = 3e5+3; int n, m, sdeg[n_]; double dp[n_], sdp[n_]; struct abc { int idx; double val; bool operator <(abc a)const { return val > a.val; } }; priority_queue<abc> pq; vector<int> gph[n_]; int main() { scanf("%d %d", &n, &m); for...
-
[BOJ] 15991 : 1, 2, 3 더하기 6
15991 : 1, 2, 3 더하기 6 풀이 둠칫타칫 코드 #include <cstdio> const int m = 1e9+9; int n, t, d[55555]={0,1,1,2,4}; int main() { for (int i = 5; i <= 55555; i++) { d[i] = ((long long)d[i-1]+d[i-2]+d[i-3]) % m; } for (scanf("%d", &t); t--;) { scanf("%d", &n); printf("%d\n", (d[n/2+1] + d[n/2]) % m); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘,...
-
[BOJ] 15990 : 1, 2, 3 더하기 5
15990 : 1, 2, 3 더하기 5 풀이 계단오르기 아니면 RGB거리 문제랑 비슷하게 풀면 된다 코드 #include <cstdio> const int m = 1e9+9; int n, t, d[3][100001]; int main() { d[0][1] = d[1][2] = d[0][3] = d[1][3] = d[2][3] = 1; for (int i = 4; i <= 100000; i++) { d[0][i] = (d[1][i-1]+d[2][i-1])%m; d[1][i] = (d[0][i-2]+d[2][i-2])%m; d[2][i] = (d[0][i-3]+d[1][i-3])%m; } for (scanf("%d", &t); t--;) { scanf("%d", &n); printf("%lld\n", ((long long)d[0][n]+d[1][n]+d[2][n])%m); } return 0; }...
-
[BOJ] 15989 : 1, 2, 3 더하기 4
15989 : 1, 2, 3 더하기 4 풀이 계단오르기 문제랑 비슷하게 풀면 된다 중복되는 경우를 배제해야 하므로 2칸 오르는 경우의 수와 3칸 오르는 경우의 수를 따로 구해주자 답은 두 값을 합친 거에 1로만 채우는 경우의 수 1을 더해주면 된다. 코드 #include <cstdio> int n, t, d[2][10001]; int main() { d[0][2] = 1; for (int i = 3; i <= 10000; i++) { d[0][i] = d[0][i-2]+1; d[1][i] = d[0][i-3]+d[1][i-3]+1; } for (scanf("%d", &t); t--;) { scanf("%d",...
-
[BOJ] 15988 : 1, 2, 3 더하기 3
15988 : 1, 2, 3 더하기 3 풀이 간다~~~~~~~~` 코드 #include <cstdio> int n, t, d[1000001]={0,1,2,4}; int main() { for (int i = 4; i <= 1e6; i++) { d[i] = ((long long)d[i-1]+d[i-2]+d[i-3]) % (int)(1e9+9); } for (scanf("%d", &t); t--;) { scanf("%d", &n); printf("%d\n", d[n]); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 14585 : 사수빈탕
14585 : 사수빈탕 풀이 코드 #include <cstdio> typedef long long ll; int n, m, x; ll r, s, a[1002]={1}; int main() { scanf("%d %d", &n, &m); while (n--) scanf("%d", &x), a[s=(s+x)%m]++; while (m--) r+=(a[m]*(a[m]-1))/2; printf("%lld", r); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2056 : 작업
2056 : 작업 풀이 간단한 다이나믹으로 풀어도 되고 위상정렬스럽게 풀어도 된다 코드 #include <cstdio> #include <algorithm> using namespace std; int n, res, dp[10001]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { int c, m, x; scanf("%d %d", &c, &m); for (int j = 0; j < m; j++) { scanf("%d", &x); dp[i] = max(dp[i], dp[x]); } res = max(res, dp[i] += c); } printf("%d", res); return 0; }...
-
[BOJ] 14226 : 이모티콘
14226 : 이모티콘 풀이 . 코드 #include <cstdio> #include <cstring> int n, dp[12345][23]; int min(int a, int b) { return a < b ? a : b; } int go(int now, int cnt) { if (now == 0 || cnt > 20) return 1e9; if (now == n) return 0; if (dp[now][cnt] != -1) return dp[now][cnt]; int ret = go(now - 1, cnt + 1) + 1; for (int i = 2; i * now...
-
[BOJ] 1415 : 사탕
1415 : 사탕 풀이 . 코드 #include <cstdio> #include <vector> using namespace std; int n, ccnt[10001]; long long d[500005]; vector<int> cvec; bool p[500005]; void getprimes() { for (int i = 2; i <= 500000; i++) p[i] = 1; for (int i = 2; i*i <= 500000; i++) if (p[i]) for (int j = i*i; j <= 500000; j += i) p[j] = 0; } int main() { getprimes(); scanf("%d", &n); int zcnt = 1; d[0]...
-
[BOJ] 1866 : 택배
1866 : 택배 풀이 , 코드 #include <cstdio> #include <algorithm> using namespace std; int n, t, h, a[3003], dp[3003]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d %d", &t, &h); sort(a + 1, a + 1 + n); for (int i = 1; i <= n; i++) { dp[i] = dp[i - 1] + a[i] * t; int cst = h; for (int j = i;...
-
[BOJ] 10265 : MT
10265 : MT 풀이 , 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; using vi = vector<int>; const int n_ = 1e3 + 1; int n, k; int a[n_], vst[n_], cyc[n_], scc[n_], dph[n_], dp[n_]; vector<int> b[n_]; int c_dfs(int now, int dep, int num) { vst[now] = num, dph[now] = dep; if (vst[a[now]] == num) return dph[now] - dph[a[now]] + 1; return c_dfs(a[now], dep + 1, num); } int s_dfs(int now, int num) {...
-
[BOJ] 14501 : 퇴사
14501 : 퇴사 풀이 . 코드 #include <cstdio> int max(int a, int b) { return a > b ? a : b; } int n, t, p, d[22]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d", &t, &p); d[i + 1] = max(d[i + 1], d[i]); d[i + t] = max(d[i + t], d[i] + p); } printf("%d", d[n]); return 0; } 아무말 백준, 백준 온라인...
-
[BOJ] 1915 : 가장 큰 정사각형
1915 : 가장 큰 정사각형 풀이 d[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1] (if a[i][j] != 0) 코드 #include <cstdio> #include <algorithm> int n, m, i, j, r, a, d[1003][1003]; int main() { scanf("%d %d", &n, &m); for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) { scanf("%1d", &a); if (!a) continue; d[i][j] = std::min({ d[i-1][j],d[i][j-1],d[i-1][j-1] }) + 1; r = std::max(r, d[i][j]); } printf("%d", r*r); return 0; } 아무말...
-
[BOJ] 4781 : 사탕 가게
4781 : 사탕 가게 풀이 윽 코드 #include <cstdio> #include <cstring> int n, m, m1, m2, dp[10001]; inline int max(int a, int b) { return a > b ? a : b; } int main() { while (1) { scanf("%d %d.%d", &n, &m1, &m2); if (!n) break; memset(dp, 0, sizeof(dp)); m = m1 * 100 + m2; int ans = 0; for (int i = 0, c, p; i < n; i++) { scanf("%d %d.%d",...
-
[BOJ] 2293 : 동전 1
2293 : 동전 1 풀이 dp[i] = 동전 i원을 만들 수 있는 방법의 수 dp[i] = dp[i - coins[]] 코드 main() { int N, K, x, i, j; int dp[10001] = { 1, }; scanf("%d %d", &N, &K); for (i = 1; i <= N; i++) { scanf("%d", &x); for (j = 0; j <= K - x; j++) dp[j + x] += dp[j]; } printf("%d", dp[K]); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon...
-
[BOJ] 10870 : 피보나치 수 5
10870 : 피보나치 수 5 풀이 엠티 가즈아~ 코드 #include <stdio.h> int n, a, b = 1; int main() { scanf("%d", &n); while (n--) { b += a; a = b - a; } printf("%d", a); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 11727 : 2xn 타일링 2
11727 : 2xn 타일링 2 풀이 끄으 코드 main() { int n, a = 0, b = 1, i; scanf("%d", &n); for (i = 0; i < n; ++i) { b += a * 2; a = b - a * 2; b %= 10007; } printf("%d", b); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 11726 : 2xn 타일링
11726 : 2xn 타일링 풀이 쓰기 귀찮다 다른 블로그에 그림이 포함된 친절한 풀이가 많으니 다른 블로그를 참고 해주시면 감사하겠습니다. 코드 #include <stdio.h> int n, dp[1010]; int main() { dp[0] = dp[1] = 1; scanf("%d", &n); for (int i = 2; i <= n; i++) dp[i] = (dp[i - 1] + dp[i - 2]) % 10007; printf("%d", dp[n] % 10007); return 0; } main(n,a,b) { scanf("%d",&n); a=b=1; while(n--) { b+=a; a=b-a; b%=10007; } printf("%d",a); } 아무말...
-
[BOJ] 1793 : 타일링
1793 : 타일링 풀이 타일링 가즈아~~~!!! 코드 #include <iostream> #include <string> #include <algorithm> using namespace std; int n; string dp[255] = { "1", "1" }; string deohagi(string a, string b) { int sum = 0; string res; while (!a.empty() || !b.empty() || sum) { if (!a.empty()) sum += a.back() - '0', a.pop_back(); if (!b.empty()) sum += b.back() - '0', b.pop_back(); res.push_back((sum % 10) + '0'); sum /= 10; } reverse(res.begin(), res.end()); return res; } int...
-
[BOJ] 2698 : 인접한 비트의 개수
2698 : 인접한 비트의 개수 풀이 그리워하면 언젠가 만나게 되는 코드 #include <stdio.h> int q, n, k, d[111][111][2]; int main() { d[1][0][0] = d[1][0][1] = 1; for (n = 2; n <= 100; n++) for (k = 0; k < n; k++) d[n][k][0] = d[n-1][k][0] + d[n-1][k][1], d[n][k][1] = d[n-1][k][0] + (k ? d[n-1][k-1][1] : 0); for (scanf("%d", &q); q--;) scanf("%d %d", &n, &k), printf("%d\n", d[n][k][0] + d[n][k][1]); return 0; } 아무말 백준, 백준 온라인...
-
[BOJ] 9084 : 동전
9084 : 동전 풀이 그리워하면 언젠가 만나게 되는 코드 #include <stdio.h> #include <string.h> int main() { int T, N, M, p, i, j, n[21], d[10001]; scanf("%d", &T); while (T--) { scanf("%d", &N); memset(n, 0, sizeof(n)); memset(d, 0, sizeof(d)); for (i = 1; i <= N; i++) scanf("%d", &n[i]); scanf("%d", &M); d[0] = 1; for (i = 1; i <= N; i++) for (j = 0; j <= M - n[i]; j++) d[j + n[i]] +=...
-
[BOJ] 1410 : 패턴의 개수
1410 : 패턴의 개수 풀이 bitmask dp를 해보자! 근데 이거 풀이를 어떻게 써야하지 dp[len][bit] = 패턴의 길이를 len까지만 놓고 볼 때, 마스킹 된 패턴에만 일치하는 길이 len짜리 문자열의 수 코드 #include <iostream> #include <string> using namespace std; const int mod = 1000003; int n, k; int dp[50][1 << 15]; string str[15]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> k; for (int i = 0; i < n; i++) cin >> str[i]; int len...
-
[BOJ] 9252 : LCS 2
9252 : LCS 2 풀이 http://codersbrunch.blogspot.kr/2016/12/9252-lcs-2.html 코드 #include <stdio.h> #include <algorithm> int dp[1234][1234]; char s1[1234], s2[1234]; void f(int i, int j) { if (!dp[i][j]) return; if (s1[i] == s2[j]) { f(i-1, j-1); putchar(s1[i]); } else dp[i-1][j] > dp[i][j-1] ? f(i-1, j) : f(i, j-1); } int main() { scanf("%s\n%s", s1 + 1, s2 + 1); int i, j; for (i = 1; s1[i]; i++) for (j = 1; s2[j]; j++) dp[i][j] = std::max({ dp[i-1][j], dp[i][j-1],...
-
[BOJ] 10251 : 운전 면허 시험
10251 : 운전 면허 시험 풀이 dp[i][j][k][d] = (i, j)까지 방향을 k번 틀고 d방향에서 왔을 때의 최소 연료량 아 졸리다 자세한 풀이는 다른 블로그를 보는 게 더 좋겠다! 코드 #include <stdio.h> #include <string.h> int min(int a, int b) { return a < b ? a : b; } int n, m, l, g, dp[102][102][102][2], gas[102][102][2]; int main() { int T; for (scanf("%d", &T); T; T--) { scanf("%d %d %d %d", &n, &m, &l, &g); for...
-
[BOJ] 1520 : 내리막 길
1520 : 내리막 길 풀이 메모이제이션 하면서 탐색해주자!! 코드 #include <stdio.h> const int dx[] = { 0,1,0,-1 }; const int dy[] = { 1,0,-1,0 }; int n, m, a[505][505], d[505][505]; int dfs(int x, int y) { if (x == n && y == m) return 1; if (~d[x][y]) return d[x][y]; d[x][y] = 0; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if...
-
[BOJ] 1947 : 선물 전달
1947 : 선물 전달 풀이 오랜만에 정상적인 풀이!! 더 자세히 알고 싶다면 구글에 완전순열 또는 교란을 검색해 보자! 증명 D[n] = (n-1) * (D[n-1] + D[n-2]) 자연수 1~n에 n+1을 더해서 완전순열을 만들어 보자. n+1은 1~n 중의 어떤 수 k의 자리에 놓인다. 이러한 k는 1부터 n까지 총 n개가 있을 수 있다. 그리고 우리는 이후의 상황을 다음의 두 경우로 나눌 수 있다. 1. n+1이 k의 자리에, k가 n+1의 자리에 놓이는 경우: k와 n+1을 제외한 나머지 n-1개의 수로...
-
[BOJ] 2775 : 부녀회장이 될테야
2775 : 부녀회장이 될테야 풀이 점화식을 오지게 세워보자~ d[i][j] = i층 j호에 사는 사람의 수 d[i][j] = d[i-1][j] + d[i][j-1] 코드 #include <stdio.h> int t, n, k, d[15][15]; int main() { for (int i = 1; i < 15; i++) d[0][i] = i; for (int i = 1; i < 15; i++) for (int j = 1; j < 15; j++) d[i][j] = d[i-1][j] + d[i][j-1]; scanf("%d", &t); while (t--) { scanf("%d %d", &k, &n);...
-
[BOJ] 11722 : 가장 긴 감소하는 부분 수열
11722 : 가장 긴 감소하는 부분 수열 풀이 죽을 것 같아도 미칠 것 같아도 하늘만 뚫어지게 보며 버텼죠 그대를 본다면 눈물을 본다면 분명 난 주저앉고 말테니 코드 #include <stdio.h> #include <algorithm> using namespace std; int n, tmp, len, a[1001], d[1001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &tmp); auto ret = lower_bound(a, a + i, tmp, [](const int &i, const int &j) { return i >...
-
[BOJ] 1562 : 계단 수
1562 : 계단 수 풀이 D[length][number][bitmask] = D[length - 1][number ± 1][bitmask | (1 << number)] 룰루랄라 코딩을 해보자~ 코드 #include <stdio.h> #include <string.h> const int mod = 1e9; int n, ans, dp[101][10][1025]; int dfs(int len, int num, int msk) { int &ret = dp[len][num][msk]; msk |= (1 << num); if (num < 0 || num > 9) return 0; if (len == n) return (msk == (1 << 10) - 1) ? 1 :...
-
[BOJ] 1727 : 커플 만들기
1727 : 커플 만들기 풀이 D[n][m] = 오름차순으로 남자 n명, 여자 m명을 짝짓는 최소의 값 D[n][m] = min(D[n-1][m-1] + abs(man[n] - woman[m]), D[n-1][m]) (if n > m) D[n][m] = min(D[n-1][m-1] + abs(man[n] - woman[m]), D[n][m-1]) (if n < m) 코드 #include <stdio.h> #include <algorithm> using namespace std; int abs(int a) { return a < 0 ? -a : a; } int n, m, a[1001], b[1001], d[1001][1001]; int main() { scanf("%d %d", &n, &m); for (int...
-
[BOJ] 8902 : 색상의 길이
8902 : 색상의 길이 풀이 잘 정리된 풀이가 있어서 풀이와 출처를 첨부합니다! 목적 함수 : Sum { Length(color) } Length(c) = LastIdx(c) - FirstIdx(c) + 1 이므로 결국, Sum { LastIdx } + Sum { -FirstIdx }를 최소화 시키는 문제로 볼 수 있다. 2개의 차 행렬은 앞에서부터 순차적으로 합쳐지기 때문에 첫 번째 차 행렬에서 i개의 차량이 합쳐지고, 두 번째 차 행렬에서 j개의 차량이 합쳐졌을 때를 상태 공간으로 삼아 동적계획법을 수행할 수 있다. 이를 D[i][j]라고 하자....
-
[BOJ] 14728 : 벼락치기
14728 : 벼락치기 풀이 띠용 이거 누가봐도 냅색인걸?! 코드 #include <stdio.h> #define max(a,b) (a)>(b)?(a):(b) int n, t, k, s, d[10001]; int main() { scanf("%d %d", &n, &t); while (n--) { scanf("%d %d", &k, &s); for (int i = t; i >= k; i--) d[i] = max(d[i], d[i - k] + s); } printf("%d", d[t]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge
-
[BOJ] 2565 : 전깃줄
2565 : 전깃줄 풀이 LIS를 구해주자! 주어진 두 축을 주어진 선으로 연결했을 때 겹치는 선이 없어야 한다! 한 축 x를 기준으로 잡아 pair를 정렬해주자. 이제 정렬한 축 x를 기준으로 한바퀴 쭉 돌면서 순서대로 마주치는 y축에 대해서 LIS를 수행해주자! 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; int n, len, lis[100]; pair<int, int> a[100]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d %d",...
-
[BOJ] 9251 : LCS
9251 : LCS 풀이 dp[i][j] = a[1~i]와 b[1~j]의 LCS 값 dp[i][j] = max(d[i-1][j], d[i][j-1], d[i-1][j-1] + (a[i] == b[j])) 코드 #include <stdio.h> #include <algorithm> char a[1111], b[1111]; int i, j, d[1111][1111]; int main() { scanf("%s\n%s", a + 1, b + 1); for (i = 1; a[i]; i++) for (j = 1; b[j]; j++) d[i][j] = std::max({ d[i-1][j], d[i][j-1], d[i-1][j-1] + (a[i] == b[j]) }); printf("%d", d[i-1][j-1]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ,...
-
[BOJ] 1965 : 상자넣기
1965 : 상자넣기 풀이 lower bound를 써주자! 더 큰 상자가 최소 어디에 들어갈 수 있는지 lower bound로 찾으면 된다! O(n^2) dp대신에 lower bound를 써주면 O(nlogn)에 풀 수 있따! 코드 #include <stdio.h> #include <algorithm> using namespace std; int n, len, a[1001]; int main() { scanf("%d", &n); while (n--) { int tmp; scanf("%d", &tmp); auto it = lower_bound(a, a + len, tmp); if (*it == 0) len++; *it = tmp; } printf("%d", len); return 0; } 아무말...
-
[BOJ] 11055 : 가장 큰 증가 부분 수열
11055 : 가장 큰 증가 부분 수열 풀이 d[i] = i번째 수까지의 부분 수열 중 최댓값으로 놓자! d[i] = d[j] + a[i] lis에서 dp 배열에 길이를 넣는 것 대신 최댓값을 넣어주면 된다. 코드 #include <stdio.h> int n, ans, a[1001], d[1001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); d[i] = a[i]; for (int j = 0; j <= i; j++) { if (a[j] < a[i] &&...
-
[BOJ] 1699 : 제곱수의 합
1699 : 제곱수의 합 풀이 knapsack 풀듯이 똑같이 풀면 된다! 배낭에 무게가 i*i이고 가치가 1인 돌덩이들을 넣는다고 생각하자! dp[j] = min(dp[j-i*i] + 1, dp[j]) 코드 #include <stdio.h> int n, d[100001]; int min(int a, int b) { return a < b ? a : b; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) d[i] = 1e9; for (int i = 1; i*i <= n; i++) for (int j =...
-
[BOJ] 1309 : 동물원
1309 : 동물원 풀이 d1[i] = 2*i인 우리에서 i번째 칸에 사자를 0마리 놓는 경우의 수 d2[i] = 2*i인 우리에서 i번째 칸의 한 쪽에만 사자를 1마리 놓는 경우의 수 d1[i] = d1[i-1] + d2[i-1] * 2 d2[i] = d1[i-1] + d2[i-1] 위의 식을 그대로 써도 좋지만, 1차원으로 더 압축해보자! 위에서 정의한 d1과 d2를 잘 기억하자. d1[i] = d1[i-1] + d2[i-1] * 2 d1[i] = (d1[i-2] + d2[i-2] * 2) + (d1[i-2] + d2[i-2]) * 2 d1[i]...
-
[BOJ] 2133 : 타일 채우기
2133 : 타일 채우기 풀이 타일은 n이 짝수인 경우에만 완벽히 채울 수 있다. 2*1 타일을 맨위와 맨아래에 일렬로 배치하는 경우에 유의하자. dp[i] = dp[i-2] * 3 + dp[i-j] * 2 (4 <= i, 4 <= j <= i) 코드 #include <stdio.h> int main() { int n, d[31] = { 1,0,3 }; scanf("%d", &n); for (int i = 4; i <= n; i += 2) { d[i] = d[i - 2] * 3; for (int j...
-
[BOJ] 2591 : 숫자카드
2591 : 숫자카드 풀이 n-1번째 숫자와 n번째 숫자로 만든 값이 10~34면 dp[n-2]를 플러스 n번째 숫자가 0보다 크면(단독으로 숫자를 구성할 수 있으면) dp[n-1]을 플러스 코드 #include <stdio.h> int i, a[44], dp[44]; int main() { dp[1] = 1; for (i = 2; ~scanf("%1d", &a[i]); i++) { if (a[i]) dp[i] += dp[i - 1]; if (a[i] + a[i - 1] * 10 > 9 && a[i] + a[i - 1] * 10 < 35) dp[i] += dp[i -...
-
[BOJ] 14568 : 2017 연세대학교 프로그래밍 경시대회
14568 : 2017 연세대학교 프로그래밍 경시대회 풀이 택희가 받는 사탕의 개수를 i로 두고 구하면 된다. n개 사탕 중에서 택희 사탕 i개와 영훈이랑 남규의 사탕 차이 2개를 뺀 사탕 갯수 n-i-2에서 (영훈 <= 남규)를 만족하는 조합의 수는 (n-i-2)/2와 같다. ex1) 5를 나누는 경우: (1,4), (2,3) ex2) 6를 나누는 경우: (1,5), (2,4), (3,3) 코드 #include <stdio.h> int n, sum; int main() { scanf("%d", &n); for (int i = 2; i <= n - 2; i += 2)...
-
[BOJ] 13910 : 개업
13910 : 개업 풀이 웍을 최대 2개까지 사용할 수 있으므로 가능한 조합을 모두 구해둔다 그리고 점화식 세워서 풀면 된다. dp[n] = min(dp[n-i]+1,dp[n]) 코드 #include <stdio.h> int main() { int n, m, i, j, a[101], dp[10001]; bool chk[22222] = { 0 }; scanf("%d %d", &n, &m); for (i = 0; i <= n; i++) dp[i] = 1e9; chk[0] = 1; dp[0] = 0; for (i = 0; i < m; i++) scanf("%d", &a[i]); for (i =...
-
[BOJ] 11057 : 오르막 수
11057 : 오르막 수 풀이 점화식을 세우자! dp[수열의 자릿수 i][i번째 자릿수의 숫자 j] 일 때의 경우의 수 dp[i][j] = dp[i-1][j] + dp[i][j-1] 코드 #include <stdio.h> const int mod = 10007; int n, i, j, ans, dp[10001][10]; int main() { scanf("%d", &n); for (i = 0; i <= 9; i++) dp[1][i] = 1; for (i = 2; i <= n; i++) { dp[i][0] = dp[i - 1][0]; for (j = 1; j <= 9; j++) {...
-
[BOJ] 11048 : 이동하기
11048 : 이동하기 풀이 간단하게 점화식을 세우면 dp[i][j] = dp[i][j] + max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])라는 식이 나온다. 다시 생각해보자. dp[i+1][j+1]을 굳이 갈 필요가 없다. 사탕의 개수가 음수가 아니기 때문에, dp[i+1][j] 또는 dp[i][j+1]을 거쳐서 dp[i+1][j+1]에 가는 값이 dp[i+1][j+1]로 바로 가는 값 보다 작아질 수 없다. 쉽게 말하자면 가로+세로(세로+가로)로 가는 값이 대각선으로 가는 값 보다 작아질 일이 없다는 것이다. 더 나가아서, dp 배열을 1차원으로 줄일 수 있다. 입력을 왼쪽위->오른쪽아래으로 받으면서 진행하게 되면 dp[j-1]은 dp[i][j-1]의 최댓값, dp[j]는 dp[i-1][j]의 최댓값이...
-
[BOJ] 1413 : 박스 안의 열쇠
1413 : 박스 안의 열쇠 풀이 모든 열쇠를 얻으러면, 열쇠들 사이에 사이클이 생겨야한다. 우리에겐 k개의 폭탄이 있기 때문에, 이 열쇠들을 k개의 집합으로 나눠서 사이클을 만드는 경우의 수를 세면 된다. n개의 원소를 k개의 원순열로 분할하기 위해, 제1종 스털링 수라는 걸 사용해보자. s(n, k) = s(n-1, k-1) + (n-1)*s(n-1, k)라는 점화식이 나온다. gcd로 최대공약수를 구하고, 합으로 나눠주면 끝! 코드 #include <stdio.h> typedef long long ll; int n, m, i, j; ll dp[21][21] = { 1 }, div;...
-
[BOJ] 11052 : 붕어빵 판매하기
11052 : 붕어빵 판매하기 풀이 dp[i] = 붕어빵 i개를 팔았을 때의 최댓값 dp[i] = i-j번째 최댓값 + j개 세트의 가격 코드 #include <stdio.h> int n, i, j, a[1001], dp[1001]; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i = 1; i <= n; i++) for (j = 1; j <= i; j++) if (dp[i] < dp[i - j] + a[j]) dp[i] = dp[i - j] + a[j];...
-
[BOJ] 1937 : 욕심쟁이 판다
1937 : 욕심쟁이 판다 풀이 dfs를 돌리자! 코드 #include <stdio.h> const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; const int n_ = 500 + 5; int n, a[n_][n_], dp[n_][n_]; inline int max(int a, int b) { return a > b ? a : b; } int dfs(int x, int y) { if (dp[x][y]) return dp[x][y]; dp[x][y] = 1; for (int i = 0; i < 4; i++) { int...
-
[BOJ] 2839 : 설탕배달
2839 : 설탕배달 풀이 dp[i] = min(dp[i-3], dp[i-5]) + 1로 두고 풀면 된다. n이 5천개니까 max를 대충 1600?쯤 잡으면 3으로 꽉채워도 최대 해보다 작고 max를 5천개 더해도 int 안쪽이니까 max를 2222로 잡았다. 코드 #include <stdio.h> int min(int a, int b) { return a < b ? a : b; } int main() { int n, i, a[5001]; scanf("%d", &n); for (i = 0; i <= n; i++) a[i] = 2222; a[3] = a[5] = 1;...
-
[BOJ] 1509 : 팰린드롬 분할
1509 : 팰린드롬 분할 풀이 나중에 써야징 코드 #include <stdio.h> #include <string.h> const int n_ = 2500 + 5; int len, dp[n_][n_], res[n_]; char data[n_]; int main() { scanf("%s", data); len = strlen(data); for (int i = 1; i <= len; i++) dp[i][i] = 1; for (int i = 1; i <= len - 1; i++) if (data[i - 1] == data[i]) dp[i][i + 1] = 1; for (int i = 2; i <= len...
-
[BOJ] 13308 : 주유소
13308 : 주유소 풀이 2016 koi 전국대회 2번 문제이다. 뭔가 코드가 dp인 것 같기도 하고 아닌 것 같기도 한데 어쨌든 다익스트라+dp 그런 느낌으로 풀었다. 음 생각해보니 dp가 맞네 dp[i][j] = 노드i에서 기름값j로 놓고 풀면 된다! 여기서 트릭(?)을 한 번 써보자. priority_queue에서 dst가 가장 작은 노드부터 꺼내기 때문에 dp[i][j] (== vst[i][j])에 방문했었다면 이미 지금보다 작은 값으로 방문했었음이 보장된다. 그래서 bfs 돌릴 때랑 똑같이 풀면 된다. visted면 방문하지 않아도 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef...
-
[BOJ] 12911 : 좋아하는 배열
12911 : 좋아하는 배열 풀이 dp[i][j] = 길이가 i이고, 첫번째 숫자가 j 나머지 연산에 주의하자. 코드 #include <stdio.h> typedef long long ll; const int mod = 1000000007; int N, K; int dp[11][100001]; ll sum[11]; int main() { scanf("%d %d", &N, &K); for (int i = 0; i <= K; ++i) dp[1][i] = 1; sum[1] = K; for (int i = 2; i <= N; ++i) { sum[i - 1] += mod; for (int j =...
-
[BOJ] 12869 : 뮤탈리스크
12869 : 뮤탈리스크 풀이 음 원래 dp로 풀려고 했는데 그냥 bfs로 풀었다. dp[i][j][k] = 1번, 2번, 3번 scv의 체력으로 두고 풀어도 된다. 코드 #include <bits/stdc++.h> using namespace std; int N, A[3], ans = 987654321; const int D[6][3] = { {1,3,9},{1,9,3},{3,1,9},{3,9,1},{9,1,3},{9,3,1} }; bool chk[61][61][61][20]; struct ABC { int a, b, c, x; ABC() {} ABC(int a, int b, int c, int x) : a(a), b(b), c(c), x(x) {} }; int main() { scanf("%d", &N); for (int...
-
[BOJ] 13302 : 리조트
13302 : 리조트 풀이 다이나믹 프로그래밍! dp[i][j] = i번째 날에 쿠폰 개수가 j인 경우의 수! 룰루랄라 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 100 + 10; const int price[] = { 0,10000,25000,37000 }; const int INF = 987654321; int n, m; int dp[n_][n_ * 2]; bool chk[n_]; void upd(int i, int j, int v) { if (dp[i][j] > v || dp[i][j] == INF) dp[i][j] = v; } int main() { scanf("%d %d",...
-
[BOJ] 7976 : 수열
7976 : 수열 풀이 좋은 풀이는 여기에 있다! 핵심은 이거: dp[i][j] = i번까지의합 % 2가 j인 최소 변환 횟수 코드 #include <stdio.h> #include <algorithm> using namespace std; int N, K; int cnt[1000001][2], dp[1000001][2]; int main() { scanf("%d %d", &N, &K); for (int i = 0; i < N; ++i) { int a; scanf("%d", &a); ++cnt[i % K + 1][a & 1]; } dp[0][1] = 1e9; for (int i = 1; i <= K; ++i) {...
-
[BOJ] 1162 : 도로포장
1162 : 도로포장 풀이 dp[노드번호i][포장갯수k]로 놓고 다익스트라를 돌리자! 원래 다익스트라에서 사용하던 dist[i]대신 dp[i][j]를 참조하면서 돌면 된다. now.dst는 지금까지 누적해 온 dst값이고, nxt.dst는 노드 사이의 거리(가중치)이다. 코드 #include <stdio.h> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int n_ = 10000 + 1; struct edg { int idx, dst, cnt; edg() {} edg(int idx, int dst) : idx(idx), dst(dst) {} edg(int idx, int dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {} bool...
-
[BOJ] 2611 : 자동차경주
2611 : 자동차경주 풀이 처음 문제를 보자마자 다익스트라 풀이를 떠올렸는데 문제를 다시 읽어보니 1번 노드를 거치지 않고 다시 원래 노드로 돌아 올 수 없다 이거 싸이클도 없고 완전 DAG잖아? 위상정렬해서 풀려고 했는데 생각해보니 dp로 풀 수 있잖아? 코드 #include <stdio.h> #include <vector> using namespace std; const int n_ = 1000 + 1; int n, m, dp[n_], route[n_]; vector<pair<int, int> > gph[n_]; int dfs(int now) { if (!dp[now] && now != 1) for (auto nxt :...
-
[BOJ] 10844 : 쉬운 계단 수
10844 : 쉬운 계단 수 풀이 점화식을 세우자 dp[i][j] = 총 i 자릿수이고, 가장 큰 자릿수의 숫자가 j인 경우의 수 = dp[i-1][j-1] + dp[i-1][j+1] 끗! 코드 #include <stdio.h> const int mod = 1e9; int n, i, j, dp[101][11], ans; int main() { scanf("%d", &n); for (i = 1; i <= 9; ++i) dp[1][i] = 1; for (i = 2; i <= n; ++i) for (j = 0; j <= 9; ++j) dp[i][j] = (dp[i -...