2021/일일 기록

2021 08 22 (일) - 백준 1149, 2193, 2579

ililillllllliilli 2021. 8. 22. 22:45

주의

모든 DP문제는 재귀로 풀리지 않는다. "일부"만 재귀로 풀릴 뿐, Top-down, Bottom-up 방식 모두 고려해야 한다.

RGB거리

https://www.acmicpc.net/problem/1149

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

  • 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
  • N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
  • i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

풀이

memoize[n][3] 을 선언하여 이전 결과값을 keep track한다.

  • memoize[n][0] : n번째 집을 Red 로 칠할 때의 비용의 최솟값
  • memoize[n][1] : n번째 집을 Green 으로 칠할 때의 비용의 최솟값.
  • [n][2] :이하 동일.

점화식 : 집을 칠하는 비용의 최솟값을 찾는 문제이기 때문에 색이 다르면서 바로 직전에 칠했던 두 색의 비용을 비교하여 최솟값을 구하고 거기에 현재 집을 칠하는 비용을 더함.

min_memo[i][1] = min(min_memo[i - 1][2], min_memo[i - 1][3]) + price[i][1];
min_memo[i][2] = min(min_memo[i - 1][1], min_memo[i - 1][3]) + price[i][2];
min_memo[i][3] = min(min_memo[i - 1][1], min_memo[i - 1][2]) + price[i][3];
image-20210822215251431

 

/*
    https://www.acmicpc.net/submit/1149
    RGB 거리
*/
#include <iostream>
#include <algorithm>

int        min_memo[1001][4];
int        price[1001][4];

using namespace std;

int        main()
{
    int        i, j;
    int        n;

    cin >> n;
    for (i = 1; i <= n; i++)
    {
        for(j = 1; j <= 3; j++)
            cin >> price[i][j];
    }

    //dp
    min_memo[1][1] = price[1][1];
    min_memo[1][2] = price[1][2];
    min_memo[1][3] = price[1][3];

    for (i = 2; i <= n; i++)
    {
        for(j = 1; j <= 3; j++)
        {
            min_memo[i][1] = min(min_memo[i - 1][2], min_memo[i - 1][3]) + price[i][1];
            min_memo[i][2] = min(min_memo[i - 1][1], min_memo[i - 1][3]) + price[i][2];
            min_memo[i][3] = min(min_memo[i - 1][1], min_memo[i - 1][2]) + price[i][3];
        }
    }
    cout << min(min(min_memo[n][1], min_memo[n][2]), min_memo[n][3]);
    cin >> n;

}

 

https://www.acmicpc.net/problem/2193

이친수

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 62874 25374 18924 38.628%

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

  1. 이친수는 0으로 시작하지 않는다.
  2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

풀이

N = 1부터 시작해서 N = k 까지 직접 이친수를 찾아가면서 규칙을 찾는다

N 이친수
1 1
2 10
3 101 100
4 1010 1001 1000
5 10101 10100 10010 10000 10001
   
   
   
   

k - 1번째 이친수 각각이 1로 끝나는지, 0으로 끝나는지에 영향을 받는다.

k - 1 번째 이친수가 1로 끝난다면, k번째 이친수의 끝에는 1을 붙일 수 없어 0으로 끝나는 이친수밖에 만들지 못하며,
k - 1번째 이친수가 0으로 끝난다면, k번째 이친수의 끝에는 1과 0 을 붙일 수 있다. 따라서, 점화관계는 다음으로 도출된다.

memo[n][0] : n자리 이친수의 0으로 끝나는 이친수 개수

memo[n][1] : n자리 이친수의 1으로 끝나는 이친수 개수

        memo[i][0] = memo[i - 1][0] + memo[i - 1][1];
        memo[i][1] = memo[i - 1][0];

주의 :

k >= p 이상부터는 memo[k][1]+ memo[k][0]가 int 범위를 넘어가므로 자료형의 범위를 크게 설정해 줄 필요가 있음.

#include <iostream>

using namespace std;

unsigned long long    memo[91][2];

int        main()
{

    int        i;
    int        n;

    cin >> n;

    memo[1][0] = 0;
    memo[1][1] = 1;
    memo[2][0] = 1;
    memo[2][1] = 0;
    for (i = 3; i <= n; i++)
    {
        memo[i][0] = memo[i - 1][0] + memo[i - 1][1];
        memo[i][1] = memo[i - 1][0];
    }

    cout << memo[n][1] + memo[n][0];
    return (0);
}

 

계단 오르기

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 91500 31384 22863 35.025%

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

img

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

img

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

  1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
  2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
  3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

풀이

풀이 방법이 생각나지않아 고생했던 문제.

이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 것이 목적인데, 모든 점수를 일일히 다 더해보는 방법도 있겠다.

일단은 주어진 그림의 최댓값을 천천히 따라가면서 규칙을 찾는다.

image-20210822223147570

1번째 계단에서의 최댓값 : 1번째 계단

2번째 계단에서의 최댓값 : 1번째 계단 + 2번째 계단

3번째 계단에서의 최댓값 : 1번째 계단 + 3번째 계단, 2번째 계단 + 3번째 계단

4번째 : ...

5번째 : ..

진행하다 보면 아래 조건때문에 문제를 푸는데 수월하지가 않다.

첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

현재 n번째 계단을 밟을때 바로 직전의 경로의 경우를 따져보면, n-1번째 계단을 밟고 현재까지 온 경우, 또는 n-2번째 계단을 밟고 현재까지 온 경우. 2가지 경우밖에 존재하지 않는다.

따라서, n번째 계단은 n-1번째 계단까지의 최댓값과 n-2번째 계단의 최댓값을 비교한 뒤, 현재 계단의 weight를 더한다고 생각한다.

n- 1, n - 2번째 계단까지 경로는 최소 2번이상 재사용되기 때문에 DP로 memoization을 하여 계산하는 시간을 줄인다.

image-20210822223848128 
/*
    계단 오르기 :
    https://www.acmicpc.net/problem/2579
*/
#include <iostream>
#include <algorithm>

using namespace  std;

int        main()
{
    int        arr[301];
    int        memo[301][3];
    int        n;
    int        i;

    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> arr[i];

    memo[1][1] = arr[1];
    memo[1][2] = 0;
    memo[2][1] = arr[2];
    memo[2][2] = arr[1] + arr[2];
    for (i = 3; i <= n; i++)
    {
        memo[i][1] = max(memo[i - 2][1], memo[i - 2][2]) + arr[i];
        memo[i][2] = memo[i - 1][1] + arr[i];
    }
    cout << max(memo[n][1], memo[n][2]);
    return (0);
}
저작자표시 (새창열림)