PS) 백준 10844, 1965, 1946, 2854, 1563 (쉬운 계단 수, 상자 넣기, 신입 사원, 문제 출제, 개근상)

10844번 쉬운 계단 수

 

별로 안어려웠다. 하지만 한번 틀렸다. 그 이유는 정수 자료형 때문.

[놓친점] 각 값을 계산해 줄 때 10억으로 나눈 나머지를 넣어주었기 때문에 자동적으로 10억 미만의 값이 나올 것이라고 착각했지만. dp[n][0] ~ dp[n][9]를 더한 값은 최대 100억이 되므로 long long자료형으로 변경해주어야 한다.

값이 커질 때, 최대 데이터를 확인하고 자료형을 체크하자!

 

#include<stdio.h>
int dp[105][15]; //dp[n][i] => 길이가 n이고, i로 끝나는 계단수의 개수

int main() {
	int n; scanf("%d", &n);
	for (int i = 1; i <= 9; i++) dp[1][i] = 1;
	dp[1][0] = 0; //길이가 1이고, 0으로 끝나는 계단수는 없다.

	for (int j = 2; j <= n; j++) {
		for (int i = 0; i <= 9; i++) {
			if (i == 0) dp[j][i] = dp[j-1][1];
			else if (i == 9) dp[j][i] = dp[j - 1][8];
			else dp[j][i] = (dp[j - 1][i - 1] + dp[j - 1][i + 1])%1000000000;
		}
	}
	long long sum = 0;
	for (int i = 0; i <= 9; i++) sum += dp[n][i];
	printf("%lld", sum % 1000000000); 
	//dp[n]의 각 값은 10억미만이지만 그걸 열번 더하므로,, 중간에 더하는 연산에서 int오버플로우 발생 가능함..
	//자료형 체크!
}

 

 

 

1965번 상자 넣기

 

정리하고 보니 가장 긴 부분수열 문제랑 같았다.

#include<stdio.h>
int arr[1005];
int dp[1005];

int main() {
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
	}
	int max = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i - 1; j++) {
			if (arr[i] > arr[j]) {
				if (dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
			}
		}
		if (max < dp[i]) max = dp[i];
	}
	printf("%d", max + 1);
}

 

 

1946번 신입사원

 

문제 이해를 잘못해서 한참 헤맸다.....

 

서류 등수를 오름차순으로 정렬 한 후 면접 등수를 배열에 저장하고, 이 배열을 가장 긴 감소하는(내림차순) 부분수열으로 찾는 DP문제인줄 알았으나 n이 최대 100만이기 때문에 n^2의 코드는 무조건 시간초과가 걸린다.

무언가 이상함을 직감하고 질문 게시판에서 답을 얻었다. 

[놓친 점] -> 문제 이해를 잘못했다.

 

[문제 설명 중]

다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

 

내가 기존에 생각했던 것은

1 1

2 3

3 2

4 4

의 데이터가 있을 때, 가장 최대 인원수를 구하는 수는 2, 즉 2번째 사람과 3번째 사람을 뽑는 경우라고 생각했다.

하지만 이 경우는 다른 모든 지원자와 비교했을 때 두 점수 중 적어도 하나가 떨어지지 않아야 한다에 모순이다. 왜냐하면 서류점수와 면접점수가 각각 1등인 지원자가 있기 때문이다.

인원수가 최대가 되게 선발하고, 선발한 지원자끼리 점수 기준을 만족시킨다면, 원래 DP 풀이가 맞지만, 이 경우에는 선택하여 선발하는 것이 아닌, 다른 사람보다 뛰어나다면 무조건 선발한다. 따라서 브루트포스로 풀어야 한다.

 

[풀이법]

1. 서류 점수 기준으로 정렬한다.

2. 서류 점수가 1등인 사람은 무조건 선발한다. 

3. 나머지 사람이 선발될 수 있는 경우는 면접 점수가 높은 경우밖에 없으므로, (서류 점수는 무조건 1등보다 낮으므로) 면접 점수가 이전 사람보다 높으면 선발한다. 

#include<stdio.h>
#include<map>
using namespace std;
int arr[100005];

int main() { //testcase t만큼 반복해야 함
	int t; scanf("%d", &t);
	int n; int a, b; 
	int sum = 0; int myeon;
	for (int k = 0; k < t; k++) {
		scanf("%d", &n);
		multimap<int, int>m; multimap<int, int>::iterator iter;
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &a, &b); m.insert({ a,b });
		}
		iter = m.begin();
		for (int i = 0; i < n; i++) {
			arr[i + 1] = (*iter).second; iter++;
		}
		myeon = arr[1]; sum++; //서류 점수가 1등인 사람은 무조건 선발한다.
		//다른 사람들의 경우, 선발될 수 있는 경우는 면접점수로 뒤집는 방법밖에 없다. (서류 등수는 1등보다 무조건 낮으므로)
		//따라서 가장 긴 수열(dp) = n^2 으로 푸는 문제가 아니라 n번 순회하면서 선택해주면 되는 문제다.
		for (int i = 2; i <= n; i++) {
			if (arr[i] < myeon) { //면접 등수가 이전 사람보다 높은 경우면 선발됨
				sum++;
				myeon = arr[i];
			}
		}
		printf("%d\n", sum);
		sum = 0;
	}
}

 

시간이 많이 걸린 이유는 정렬을 위한 multimap을 써서 그런듯.

 

#include<stdio.h>
#include<map>
using namespace std;
int arr[2][100005];

int main() { //testcase t만큼 반복해야 함
	int t; scanf("%d", &t);
	int n; int a, b; int max;
	for (int k = 0; k < t; k++) {
		scanf("%d", &n);
		multimap<int, int>m;
		multimap<int, int>::iterator iter;
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &a, &b); m.insert({ a,b });
		}
		iter = m.begin();
		for (int i = 0; i < n; i++) {
			arr[0][i + 1] = (*iter).second;
			iter++;
		}
		max = -1;
		for (int i = 2; i <= n; i++) { // 5 6 3 2 1
			for (int j = 1; j <= i - 1; j++) { //가장 긴 감소하는 부분 수열 => 백 퍼 시간초과 날듯
				if (arr[0][i] <= arr[0][j]) {
					if (arr[1][i] < arr[1][j] + 1) arr[1][i] = arr[1][j] + 1;
				}
			}
			if (max < arr[1][i]) max = arr[1][i];
		}
		printf("%d\n", max + 1);
		for (int i = 0; i <= n; i++) arr[1][i] = 0;
	}
}

DP로 착각한 풀이 => 시간초과

 

2854번 문제 출제

 

점화식이 복잡했던 문제이다.

이전에 사용했던 문제에 따라서 이후에 사용할 수 있는 문제의 경우가 달라지므로(만약 1단계에 1 또는 2의 문제를 사용한 경우 2단계에 1 또는 2의 문제를 쓸 때 하나의 경우를 빼주어야 하는 등), 각 문제의 단계마다 i점 문제를 사용한 경우, i-0.5점의 문제를 사용한 경우, i+0.5문제를 사용한 경우의 수로 나누어서 배열을 선언하고 각각을 초기화해준다.

 

dp[i][1]= i단계의 문제를 사용 / dp[i][2]= i-0.5단계의 문제를 이용 / dp[i][3]= i+0.5단계의 문제를 이용

 

[풀이법]

dp[i][1] = ((dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) * arr1[i]) % ll;

i단계의 문제를 사용하는 경우의 수 = 이전 단계의 모든 경우의 합 * i단계의 문제 수

 

dp[i][2] = ((dp[i - 1][1] + dp[i - 1][2]) * arr2[i - 1] + dp[i - 1][3] * (arr2[i - 1] - 1)) % ll;

i-0.5단계의 문제를 사용하는 경우의 수 = (이전 단계에서 i-1단계, i-1.5단계를 사용하는 경우의 수)* i-0.5단계의 문제 수 +(이전 단계에서 i-1+0.5=i-0.5단계를 사용하는 경우의 수)* i-0.5단계의 문제 수에서 1을 빼준 값 ->왜냐면 같은 곳에서 문제를 빼서 쓰므로 이전 단계에서 써 준 문제는 빼주어야 함

dp[i][3] = ((dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) * arr2[i]) % ll;

i+0.5단계의 문제를 사용하는 경우의 수 = dp[i][1]과 같은 원리 

 

[놓친점]

dp배열을 int로 선언하면 왜 틀린 것인지 모르겠다. 어짜피 100000007을 나눈 값을 넣어주기 때문에 int내의 범위에서 실행된다고 생각했는데 틀렸다고 나왔다. 점화식은 문제가 없는 것 같아 혹시나 해서 자료형을 바꿔보니 통과하길래 ㅇㅅㅇ 당황함요.

 

#include<stdio.h>
#define ll 1000000007;
long long arr1[100005]; //난이도가 i인 문제의 개수
long long arr2[100005]; //난이도가 i또는 i+1인 문제의 개수
long long dp[100005][4];

int main() {
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &arr1[i]);
	for (int i = 1; i <= n - 1; i++) scanf("%d", &arr2[i]);
	dp[1][1] = arr1[1]; dp[1][2] = 0; dp[1][3] = arr2[1];
    
	for (int i = 2; i <= n; i++) {
		dp[i][1] = ((dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) * arr1[i]) % ll;
		dp[i][2] = ((dp[i - 1][1] + dp[i - 1][2]) * arr2[i - 1] 
        			+ dp[i - 1][3] * (arr2[i - 1] - 1)) % ll;
		dp[i][3] = ((dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) * arr2[i]) % ll;
	}
	long long sum = dp[n][1] + dp[n][2] + dp[n][3];
	printf("%lld", sum % 1000000007);
}

 

 

1563번 개근상

 

#include<stdio.h>
int dp[1005][4];
int zigak[1005]; //i번째 날에 지각한 경우의 수

int main() {
	int n; scanf("%d", &n);
	dp[1][1] = 1; dp[1][2] = 1; dp[1][3] = 0; 
	zigak[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i][1] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % 1000000;
		dp[i][2] = dp[i - 1][1];
		dp[i][3] = dp[i - 1][2];
		zigak[i] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % 1000000;
	}
	long long sum = 0;  long long a;
	sum = dp[n][1] + dp[n][2] + dp[n][3];
	for (int i = 1; i <= n - 1; i++) {
		a = (dp[n - i][1] + dp[n - i][2] + dp[n - i][3]) % 1000000; //???>?
		sum += (zigak[i] * a)% 1000000;
	}
	sum += zigak[n]; //마지막 날 지각을 한 경우는 따로 더해줌
	printf("%lld", sum % 1000000);
}