백준 2718 타일 채우기
음 ,, 어 바로 맞았네? (왜??.? 놀람요)
이전에 비슷한 타일 채우기 문제를 접해본 적 있었기 때문에, 이전과 비슷하게 풀었다.
뒤에서 추가될 수 있는 타일의 종류를 찾고, 더해주는 방식이다. 그러나 이렇게 문제가 복잡해지면 뒤에서 추가될 수 있는 타일의 종류가 많아지므로, 놓치는 타일이 있을 수 있어 비효율적이다. (야매임..) 조금 더 세분화된 dp를 이용해서 풀어보자!!
#include<stdio.h>
long long dp[30];
int main() {
int t; scanf("%d", &t);
int n;
dp[1] = 1; dp[2] = 5;
int a; int b;
for (int i = 3; i <= 30; i++) {
a = 4; b = 3;
dp[i] += (dp[i - 1] + dp[i - 2] * 4);
while (a <= i-1) { //짝수개일때 특이무늬 3개
dp[i] = dp[i] + dp[i-a]*3;
a = a + 2;
}
while (b <= i-1) { //홀수개일때 특이무늬는 2개!!
dp[i] = dp[i] + dp[i-b] * 2;
b = b + 2;
}
if (i % 2 == 0) dp[i] = dp[i] + 3;
else dp[i] = dp[i] + 2;
}
while (t > 0) {
scanf("%d", &n);
printf("%lld\n", dp[n]);
t--;
}
}
2591번 숫자카드
어려웡
dp[i][1] = i번째 자리에서 수를 이전의 수와 연결지어 카드를 만드는 경우 => 11
dp[i][0] = i번째 자리의 수를 새로운 카드로 만드는 경우 => 1,1
이전에 연결지어 카드를 만든 경우와, 그렇지 않은 경우에 따라서 이후에 만들 수 있는 카드가 달라지므로 두 경우를 분리하여 배열을 선언했다.
[놓친 부분]
한번 틀리고 찾은 반례 두개 1111, 1020
첫번째 반례에서 구현을 잘못해 준 부분을 발견하여 수정했다.
두번째 반례에서 0이 들어올 경우, 이 0은 무조건 앞 수와 분리할 수 없다!!(카드는 1-34이므로, 10, 20, 30만 가능) 코드에서 예외로 처리해준다.
맞았지만, 뭔가 해결방법이 확실한 채로 구현해서 맞은 게 아니라, 하다 보니 확실해진 느낌?이라서 다시 한번 풀어봐야겠다.
1. 수를 string으로 입력받고, 2자리씩 탐색하면서 34보다 작은 수의 여부를 arr배열에 저장한다.
2. 앞에서부터 수를 탐색하면서 dp배열을 완성한다.
점화식을 살짝 설명하자면
7 1 2
i
if (arr[i - 1] == 0 && arr[i] == 1) { //이전의 수가 연결될 수 없고, 현재 수가 연결될 수 있을 때 (712)
이전 수는 연결될 수 없으므로 i-1값이 담긴 카드가 마지막 카드이다.
dp[i][0] += dp[i - 1][0]; //현재 수가 연결되지 않는 경우(카드 1, 2)에는 이전 수가 연결되지 않는 경우의 수를 더해준다.
dp[i][1] += dp[i - 1][0]; //현재 수가 연결되는 경우(카드12)에는 이전 수가 연결되지 않는 경우의 수를 더해준다.
맨 앞의 조건문의 dp점화식만 설명했는데, 나머지도 생각해서 구현해주면 된다.
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
int arr[45]; //index 2 to len
long long dp[45][2];
int main() {
string input;
cin >> input;
int len = input.length();
//init arr
for (int i = 2; i <= len; i++) {
if (input[i - 2] == '2'||input[i-2]=='1' || (input[i-2]=='3' && int(input[i-1]) - 48<=4)) {
arr[i] = 1;
}
}
dp[1][0] = 1; arr[1] = 0;
for (int i = 2; i <= len; i++) {
if (input[i-1] == '0') { //0인 경우 앞수와 분리할 수 없다!
dp[i][1] += dp[i - 1][0];
}
else if (arr[i - 1] == 0 && arr[i] == 1) {
dp[i][0] += dp[i - 1][0];
dp[i][1] += dp[i - 1][0];
}
else if (arr[i - 1] == 0 && arr[i] == 0) {
dp[i][0] += dp[i - 1][0];
}
else if (arr[i - 1] == 1 && arr[i] == 0) {
dp[i][0] += (dp[i - 1][0] + dp[i - 1][1]);
}
else {
dp[i][1] += dp[i - 1][0];
dp[i][0] += (dp[i - 1][1] + dp[i-1][0]); //!!
}
}
printf("%lld", dp[len][1] + dp[len][0]);
}
2631 줄 세우기
dp공부 초반(초반이라고 해봤자 일주일 전..)에 도전했는데 너무 어려워서 건너뛰었던 문제이다.
여러 문제를 접한 뒤 다시 보니 뭐야 완전 괜찮은데? 그냥 가장 긴 증가하는 부분수열을 구하고, 이 수열에 방해가 되는 아이들을 이동시키면 된다.
가장 긴 증가하는 부분수열 문제는 여러 방향으로 응용 될 여지가 있다.
#include<stdio.h>
int dp[205][2];
int main() {
//가장 긴 증가하는 부분수열 응용 아님?
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &dp[i][0]);
dp[i][1] = 1;
}
int max = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i-1; j++) {
if (dp[j][0] < dp[i][0]) {
if (dp[j][1] + 1 > dp[i][1]) { //길이
dp[i][1] = dp[j][1] + 1;
}
}
}
if (dp[i][1] > max) max = dp[i][1];
}
printf("%d", n - max);
}
2698번 인접한 비트의 개수
처음에 한번 틀림 그 이유는,,,,,, n이 최대 100인데, 배열도 100으로 선언함. 더군다나 구현하기 편하라고 index 1부터 넣어줘서 값을 다 못담음.. 배열 크기 항상 넉넉히 선언해주기!! 기억...
점화식은 어렵지 않았지만, 초기 값 설정이 헷갈렸던 문제.
#include<stdio.h>
long long dp[101][2][101];
int main() {
int t; scanf("%d", &t);
int n, k;
while (t > 0) {
scanf("%d%d", &n, &k);
dp[1][0][0] = 1; dp[1][1][0] = 1;
for (int i = 2; i <= n; i++) {
dp[i][0][0] = dp[i - 1][0][0] + dp[i - 1][1][0];
dp[i][1][0] = dp[i - 1][0][0];
for (int j = 1; j <= k; j++) {
dp[i][0][j] = dp[i - 1][0][j] + dp[i - 1][1][j];
dp[i][1][j] = dp[i - 1][1][j - 1] + dp[i - 1][0][j];
}
}
printf("%lld\n", dp[n][0][k] + dp[n][1][k]);
t--;
}
}
'코딩) PS 공부 [백준]' 카테고리의 다른 글
PS) 백준 1720번 (타일 코드) 너ㅓㅓㅓㅓㅓㅓㅓ무 하기 싫고 안풀리는날인데 짜증나아 (0) | 2021.05.06 |
---|---|
PS) 3/23 공부 시작, 3-4월의 기록 (78sol, 브론즈 5로 시작하다) (0) | 2021.05.05 |
PS) 백준 1958, 2225, 17069, 17070, 1655번 (LCS3, 합분해, 파이프 옮기기1, 2, 가운데를 말해요) (0) | 2021.05.04 |
PS) 백준 1309, 10164번 (동물원, 격자상의 경로) (0) | 2021.05.02 |
PS) 백준 10844, 1965, 1946, 2854, 1563 (쉬운 계단 수, 상자 넣기, 신입 사원, 문제 출제, 개근상) (0) | 2021.05.01 |
댓글