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);
}
'코딩) PS 공부 [백준]' 카테고리의 다른 글
| PS) 백준 1720번 (타일 코드) 너ㅓㅓㅓㅓㅓㅓㅓ무 하기 싫고 안풀리는날인데 짜증나아 (0) | 2021.05.06 |
|---|---|
| PS) 3/23 공부 시작, 3-4월의 기록 (78sol, 브론즈 5로 시작하다) (0) | 2021.05.05 |
| PS) 백준 2718, 2591, 2631, 2698번 (타일 채우기, 숫자카드, 줄 세우기, 인접한 비트의 개수) 골드 3으로 승급! (0) | 2021.05.05 |
| PS) 백준 1958, 2225, 17069, 17070, 1655번 (LCS3, 합분해, 파이프 옮기기1, 2, 가운데를 말해요) (0) | 2021.05.04 |
| PS) 백준 1309, 10164번 (동물원, 격자상의 경로) (0) | 2021.05.02 |
댓글