백준 1720번 타일코드
계속 등장하는 타일 문제... 이번 문제는 중간에 헷갈려서 시간을 많이 허비했다.
처음에는 좌우 대칭인 코드의 수, 좌우 대칭이 아닌 코드의 수를 따로 계산하려고 했는데, 좌우 대칭인 코드를 구하는 것은 쉽다. 길이-2의 경우에 각각 앞뒤에 2*1사각형 추가, 길이-4인 경우에 각각 앞뒤에 2*2, 1*2*2인 사각형 추가해주면 된다.
반면에 좌우 대칭이 아닌 코드의 수를 어떻게 구할지 막막했다. 규칙도 없고 이전 상황을 저장할 수도 없고,,, 그러나 조금 더 생각해보니 그냥 전체 경우의 수에서 좌우 대칭인 경우의 수를 빼면 바로 나오는 것 아닌가.... 아 이걸 왜 크게 고민한걸까 ㅠㅠ
좌우 대칭인 코드는 전체에서 하나만 존재하고, 좌우 대칭이 아닌 코드는 뒤집을 시 짝이 하나씩 존재하므로 전체 경우의 수에서 좌우 대칭이 아닌 코드의 절반을 빼 준 것이 답이 된다.
dp는 풀고 나면 쉽게 보인단 말이지.. 코드도 짧고,,, 그러나 생각하기까지가 암흑같다..
#include<stdio.h>
int dp[35]; //전체 경우의 수
int dp2[35]; //좌우 대칭인 경우의 수
int main() {
int n; scanf("%d", &n);
//전체 경우의 수
dp[1] = 1; dp[2]=3;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] * 2;
}
//좌우대칭인 경우의 수
dp2[1] = 1; dp2[2] = 3; dp2[3] = 1; dp2[4] = 5;
for (int i = 5; i <= n; i++) {
dp2[i] = dp2[i - 2] + dp2[i - 4] * 2;
}
printf("%d", dp[n] - (dp[n] - dp2[n])/2);
}
2228 구간 나누기(unsol)
결국은 못푼 문제/..ㅣㅏ; 진짜 너무 어렵고 예제는 돌아가지만 반례 발견해서 수정하다가 그냥 다음에 풀기로 한다...
문제도 안풀리고 다 어렵고 .. 오늘 완전 멘탈...터진다~&($&*&$
#include<stdio.h>
#include<math.h>
int arr[105]; //i까지의 연속합
int dp[105][55]; //첫번째부터 i번까지의 수들 중 m개의 구간을 선택했을 때 구간 합의 최댓값
int main() {
int n, m; scanf("%d%d", &n, &m);
int a;
for (int i = 1; i <= n; i++) {
scanf("%d", &a);
arr[i] = arr[i - 1] + a;
}
int max; dp[1][1] = arr[1];
for (int i = 2; i <= n; i++) {
//구간이 1개일 때
dp[i][1] = dp[i - 1][1];
for (int j = i; j >= 1; j--) {
if (arr[i] - arr[j - 1] > dp[i][1]) {
dp[i][1] = arr[i] - arr[j - 1];
}
}
for (int j = 2; j <= m; j++) {
if (i < 2*j-1) break;
//i번째 숫자를 포함하지 않는 경우
max = dp[i - 1][j];
//i번째 숫자를 포함하여 새로운 구간을 만드는 경우
for (int k = i; k >= 3; k--) {
if (max < (arr[i] - arr[k - 1] + dp[k - 2][j - 1])) {
max = arr[i] - arr[k - 1] + dp[k - 2][j - 1];
}
}
dp[i][j] = max;
}
}
printf("%d", dp[n][m]);
}
자두 unsol
어려워 ...................................... 결국 못 품 하 자두가 싫어질라그럼... 자두는 죄가 없어..... ㅏㅏ
#include<stdio.h>
#include<math.h>
int arr[1005][3]; //특정 나무에서의 자두의 누적합
int dp[1005][3][35];
int main() {
int t, w; scanf("%d%d", &t, &w);
int max1, max2; int a; int max = 0;
for (int i = 1; i <= t; i++) {
scanf("%d", &a);
if (a == 1) { arr[i][1] = arr[i - 1][1] + 1; arr[i][2] = arr[i - 1][2]; }
else { arr[i][2] = arr[i - 1][2] + 1; arr[i][1] = arr[i - 1][1]; }
}
dp[1][1][0] = arr[1][1]; dp[1][2][0] = arr[1][2];
dp[1][1][1] = arr[1][2]; dp[1][1][1] = arr[1][1];
for (int i = 2; i <= t; i++) {
//시작 후 계속 제자리에 있는 경우
dp[i][1][0] = arr[i][1]; dp[i][2][0] = arr[i][2];
printf("%d %d\n", dp[i][1][0], dp[i][2][0]);
for (int j = 1; j <= w; j++) {
//이전에서 움직이지 않은 경우
max1 = dp[i - 1][1][j - 1] + arr[i][1] - arr[i - 1][1];
max2 = dp[i - 1][2][j - 1] + arr[i][2] - arr[i - 1][2];
for (int k = 0; k <= i - 1; k++) {
if(max1 < dp[k][2][j - 1] + arr[2][i] - arr[2][k])
max1 = dp[k][2][j - 1] + arr[2][i] - arr[2][k];
if (max2 < dp[k][1][j - 1] + arr[1][i] - arr[1][k])
max2 = dp[k][1][j - 1] + arr[1][i] - arr[1][k];
}
dp[i][1][j] = max1; dp[i][2][j] = max2;
printf("%d %d\n", dp[i][1][j], dp[i][2][j]);
}
}
printf("%d", max);
}
오늘 슬프다
댓글