PS) 백준 2718, 2591, 2631, 2698번 (타일 채우기, 숫자카드, 줄 세우기, 인접한 비트의 개수) 골드 3으로 승급!

백준 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--;
	}
}