KOTIP 1일차

#1. 이친수

시간 제한	메모리 제한
1.0 초	512 MB

문제

0과 1로 이루어진 이진수중 다음 성질을 만족하는 수를 이친수라고 한다.

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

예를 들면 1, 10, 100 등이 이친수가 된다.

하지만 010이나 110은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

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

입력

첫째 줄에 N이 주어진다.

출력

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

입력 예제

3

출력 예제

2

힌트

다이나믹 프로그래밍(DP)

소스

#include <stdio.h>

#define LL long long

 

int N;

LL d[2][91];

LL dp(int num, int ord) {

    if (ord == N) return 1;

    LL *ret = &d[num][ord];

    if (*ret != -1) return *ret;

    *ret = dp(0, ord + 1);

    if (num == 0) *ret += dp(1, ord + 1);

    return *ret;

}

int main() {

    scanf("%d", &N);

    for (int i = 1; i <= N; i++)

        d[0][i] = d[1][i] = -1;

    printf("%lld", dp(1,1));

}

#2. 인접한 비트의 개수

시간 제한	메모리 제한
1.0 초	512 MB

문제

0과 1로 이루어진 수열 S가 있다.

S의 첫 수를 s1, 마지막 수를 sn이라고 할 때, S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.

s1 x s2 + s2 x s3 + s3 x s4 + ... + sn-1 x sn

위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.

수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.

예를 들어, n이 5이고, k가 2이면, 수열 S가 될 수 있는 수열은 다음과 같이 6가지가 있다.

11100, 01110, 00111, 10111, 11101, 11011

입력

첫째 줄에 테스트 케이스의 수 T(1<=T<=1,000)가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, 숫자 3개가 공백으로 구분되어 이루어져 있다.

첫 번째 숫자는 테스트 케이스의 번호인 t이고, 두 번째 숫자는 n, 세 번째 숫자는 k이다.

n은 100을 넘지 않는다.

출력

각 테스트 케이스에 대해 테스트 케이스 번호와 인접한 비트의 개수가 k인 수열 S의 개수를 사이에 공백을 두고 한 줄에 하나씩 출력한다.

이 값은 2,147,483,647보다 작거나 같다.

입력예제

10
1 5 2
2 20 8
3 30 17
4 40 24
5 50 37
6 60 52
7 70 59
8 80 73
9 90 84
10 100 90

출력 예제

1 6
2 63426
3 1861225
4 168212501
5 44874764
6 160916
7 22937308
8 99167
9 15476
10 23076518

힌트

다이나믹 프로그래밍(DP)

소스

#include <stdio.h>

 

int N, K, test_case;

int d[101][101][2];

int f[101] = { 0 };

int fibo(int n) {

    if (n < 1) return 1;

    if (n == 1) return 2;

    if (n == 2) return 3;

    int *ret = &f[n];

    if (*ret != 0) return *ret;

    *ret = fibo(n - 1) + fibo(n - 2);

    return *ret;

}

int dp(int n, int k, int e) {

    if (k == 0) return fibo(n-2);

    if (n == 1) return 0;

    int *ret = &d[n][k][e];

    if (*ret != -1) return *ret;

    *ret = 0;

    if (e==1)

    {

        *ret += dp(n - 1, k - 1, 1) + dp(n - 1, k, 0);

    }

    else

    {

        *ret += dp(n - 1, k, 1) + dp(n - 1, k, 0);

    }

    return *ret;

}

int main() {

    int T;

    scanf("%d", &T);

    for (int i = 1; i <= T; i++)

    {

        scanf("%d %d %d", &test_case, &N, &K);

        for (int i = 0; i <= N; i++)

        {

            for (int j = 0; j <= N; j++)

            {

                d[i][j][0] = d[i][j][1] = -1;

            }

        }

        printf("%d %d\n", test_case, dp(N, K, 0) + dp(N, K, 1));

    }

}

#3. 롤러코스터

시간 제한	메모리 제한
1.0 초	512 MB

문제

소들은 롤러코스터를 짓고있다! 소들은 자신들이 가지고 있는 돈을 활용해서 최대한 재밌는 롤러코스터를 만들고 싶어한다.

롤러코스터는 길이 L(1<=L<=1,000)의 직선형 롤러코스터이다. 소들이 롤러코스터를 지을 때 롤러코스터는 N(1<=N<=10,000)개의 교체 가능한 부품들중 일부로 구성되어야 한다.

각 부품i는 고정된 길이 Wi(1<= Wi <= L)를 가지고 있다. 그리고 다양한 지형의 굴곡 때문에, i번째 부품은 오직 Xi(0<= Xi <= L-Wi)의 위치를 시작점으로만 놓을 수 있다.

소들은 다양한 롤러코스터를 0부터 L까지 빈틈없이 채우고 싶어한다. 만약 중간에 빈칸이 있으면 롤러코스터를 구성할 수 없다. 또한 각 부품끼리 겹쳐서 롤러코스터를 건설하는 경우도 없다.

각 i번째 부품은 "재미도" Fi(1<= Fi <= 1,000,000)과 짓는데 드는 비용 Ci(1<= Ci <= 1000)를 가지고 있다. 총 비용은 롤러코스터를 구성하는 부품을의 비용의 합으로 계산된다. 마찬가지로 총 재미도의 합은 롤러코스터를 구성하는 부품들의 재미도의 합으로 계산된다.

소들의 총 예산은 B(1<= B<= 1000)이다. 소들을 도와 예산내에서 가장 큰 재미도를 가진 롤러코스터를 지을 수 있도록 도와주자!

입력

첫번째 줄은 세개의 정수로 구성된다: L, N, B

두번째 줄부터 N+1번째 줄은 각 i번째 부품들의 Xi, Wi, Fi, Ci가 공백으로 구분되어서 주어진다.

출력

소들이 예산안에 각 부품들을 가지고 지을 수 있를 롤러코스터의 최대 재미도의 합을 출력한다.

만약 롤러코스터를 짓는 방법이 없다면 -1을 출력한다.

입력 예제

5 6 10
0 2 20 6
2 3 5 6
0 1 2 1
1 1 1 3
1 2 5 4
3 2 10 2

출력 예제

17

힌트

다이나믹 프로그래밍(DP)

소스

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define LL long long

#define MAX 100000000000

 

int L, N, B;

struct st {

    int w;

    int f;

    int c;

};

struct st block[10001][10001];

int order[10001] = { 0 };

__inline LL max(LL a, LL b) {

    return a > b ? a : b;

}

LL d[1001][1001] = { 0 };

LL Ans;

LL dp(int n, int cost) {

    if (n == L) return MAX;

    if (cost == B) return 0;

    LL *ret = &d[n][cost];

    if (*ret != 0) return *ret;

    for (int i = 0; i < order[n]; i++)

    {

        if (block[n][i].c + cost <= B) {

            *ret = max(*ret, (LL)block[n][i].f + dp(n + block[n][i].w, cost + block[n][i].c));

        }

    }

    return *ret;

}

 

int main() {

    scanf("%d %d %d", &L, &N, &B);

    for (int i = 0; i < N; i++)

    {

        int tmp;

        scanf("%d", &tmp);

        scanf("%d %d %d", &block[tmp][order[tmp]].w, &block[tmp][order[tmp]].f, &block[tmp][order[tmp]].c);

        order[tmp]++;

    }

    Ans = dp(0, 0);

    if (Ans > MAX) Ans %= MAX;

    else Ans = -1;

    printf("%lld", Ans);

}

#4. N_QUEEN

시간 제한	메모리 제한
1.0 초	256 MB

문제

N_Queen문제는 유명한 문제이다. 이는 N*N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하시오.

시간제한: 1초

입력

첫째 줄에 자연수 N이 주어진다.(1<=N<=12)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

입력 예제

4

출력 예제

2

힌트

깊이우선탐색(DFS), (하지만 N이 엄청 커진다면?)

소스

#include <stdio.h>

 

 

int N;

int chk[13];

int no_submit;

int dfs(int n) {

    if (n == N + 1) return 1;

    int ret = 0;

    for (int i = 1; i <= N; i++)

    {

        no_submit = 0;

        for (int j = 1; j < n; j++)

        {

            if (chk[j] + n - j == i || chk[j] - (n - j) == i || chk[j] == i) {

                no_submit = 1;

                break;

            }

        }

        if (no_submit == 1) continue;

        chk[n] = i;

        ret += dfs(n + 1);

    }

    return ret;

}

int main() {

    scanf("%d", &N);

    printf("%d", dfs(1));

}

#5. 소수경로

시간 제한	메모리 제한
1.0 초	512 MB

문제

형석이는 다음날 SDS에 강의를 하러 간다. 하지만 아침에 일찍 일어나야 한다는 부담감에 고급 알람 시계를 준비하였다. 최근에 화장실 사진찍기, 뺨 때리기, 냄새 뿌리기 등의 알람 시계가 나오고 있지만, 형석이는 강의를 위해 머리를 써야 끌 수 있는 알람을 준비하였다.

이 시계의 시간을 맞춰 놓고, 그 시간이 되어 울리기 시작하면, 4자리의 소수 2개가 고급 알람 시계에 표시된다. 첫 번째 적혀 있는 수는 숫자를 변경할 수 있게 되어있다. 그럼 이제 알람을 끄는 방법은 간단하다. 첫 번째 적혀 있는 소수를 두 번째 적혀 있는 소수로 변경하면 된다. 이때, 한번에 한자리만 변경할 수 있고, 한자리를 변경하였을 때, 변경된 수는 소수이어야 한다. 또한 4자리 소수이기 때문에, 경로 중간에도 4자리를 유지해야한다. (즉, 1000이상의 소수) 형석이는 알람이 계속 울리는 것이 싫기 때문에, 최대한 빠르게 알람을 끄고 싶어한다. 형석이를 도와 어떻게 하면 최소한의 단계로 첫 번째 소수를 두 번째 소수로 변경할 수 있는지 구하시오.

예를 들어서 1033이라는 수를 8179로 변경한다면, 1033 1733 3733 3739 3779 8779 8179의 순서로 변경이 가능하다.

시간제한: 1초

입력

입력의 첫 줄에는 테스트 케이스를 나타내는 T가 주어진다. 각 테스트 케이스의 첫 줄에는 고급 알람 시계에 적혀 있는 두 개의 소수가 빈칸을 사이에 두고 주어진다. (1000<=소수<=9999)

출력

각 테스트 케이스별로 한 줄에 정답을 출력한다. 정답은 두 번째 소수로 변경하는 최소한의 단계수이다.

입력 예제

3
1033 8179
1373 8017
1033 1033

출력 예제

6
7
0

힌트

너비우선탐색(BFS)

소스

#include <stdio.h>

__inline int min(int a, int b) {

    return a < b ? a : b;

}

int N, M;

int prime[10000] = { 0 };

int queue[10000];

int s, e;

int main() {

    int T;

    scanf("%d", &T);

    for (int i = 2; i < 100; i++)

    {

        int n = i;

        while (n < 10000)

        {

            prime[n] = 1;

            n += i;

        }

    }

    for (int test_case = 1; test_case <= T; test_case++)

    {

        int chk[10000] = { 0 };

        scanf("%d %d", &N, &M);

        if (N == M) {

            printf("0\n");

            continue;

        }

        chk[N] = 0;

        s = e = 0;

        queue[e] = N;

        e++;

        while (s < e)

        {

            int n = queue[s];

            s++;

            int idx = 1;

            for (int j = 0; j < 4; j++)

            {

                int pivot = (n / idx) % 10;

                for (int i = 0; i <= 9; i++)

                {

                    int next = n + (i - pivot)*idx;

                    if (next == N || chk[next] > 0 || prime[next] == 1 || (idx == 1000 && i == 0)) continue;

                    queue[e] = next;

                    e++;

                    chk[next] = chk[n] + 1;

                    if (next == M) goto loop;

                }

                idx *= 10;

            }

        }

    loop:;

        printf("%d\n", chk[M]);

    }

}

#6. 동굴

시간 제한	메모리 제한
2.0 초	512 MB

문제

벌레 한 마리가 동굴을 지나려고 한다. 모두가 알다시피 동굴은 석순과 종유석이 굉장히 많은 공간이다. 이 벌레는 이렇게 장애물이 많은 동굴을 지나갈 것이다. 동굴의 길이는 N미터이고, 높이는 H미터이다. N은 항상 짝수이고, 장애물은 석순과 종유석이 번갈아 가면서 등장하고, 첫 장애물을 항상 석순이다.

아래 예제는 N=14, H =5의 예이다.

남자다운 이 벌레는 장애물을 굳이 피하지 않는다. 즉, 처음 정한 높이에서 일직선으로 장애물을 부수면서 지나간다. 벌레가 아래에서 4번째 구간으로 지나가면, 아래 그림과 같이 8개의 장애물을 부수게 된다.

하지만, 첫 번째나 다섯 번째 구간으로 날아간다면 벌레는 7개의 장애물만 부시면 된다.

벌레는 아픔을 느끼는 남자이기 때문에, 최소한의 장애물만 부시고 싶어한다. 여러분은 이 벌레가 최소 몇 개의 장애물만 부수고도 통과할 수 있는지 구하고, 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

시간제한: 1초

입력

첫째 줄에 N과 H가 주어진다. N은 짝수이다. (2<=N<=200,000, 2<=H<=500,000)

다음 N개의 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최소값과 그러한 구간의 수를 공백으로 구분하여 출력하시오.

입력 예제

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

출력 예제

7 2

힌트

Indexed Tree(segment tree) / 구간 업데이트

소스

#include <stdio.h>

int main() {

int N, H;

scanf("%d %d", &N, &H);

int n;

for (n = 1; n < H; n <<= 1);

n--;

int tree[1048576] = { 0 };

int idx = 0;

int low, hi;

for (int i = 0; i < N; i++)

{

int L;

scanf("%d", &L);

if (idx) {

hi = n + H;

low = n + H - L+1;

}

else

{

low = n + 1;

hi = n + L;

}

while (low <= hi)

{

if (low & 1) tree[low]++;

if (!(hi & 1)) tree[hi]++;

low = (low + 1) >> 1;

hi = (hi - 1) >> 1;

}

idx = (idx + 1) & 1;

}

int num[200001] = { 0 };

int min = 987654321;

for (int i = n+1; i <= n+H; i++)

{

int hi = i>>1;

while (hi>0)

{

tree[i] += tree[hi];

hi >>= 1;

}

num[tree[i]]++;

if (min > tree[i]) min = tree[i];

}

printf("%d %d", min, num[min]);

}

#7. 등산

시간 제한	메모리 제한
2.0 초	512 MB

문제

최근 출시된 오버워치가 지루해진 형석이는 등산이나 하기로 결정했다. 형석이는 산의 시작점부터 도착지점까지 산을 오르락~ 내리락~ 하면서 간다. 하지만 형석이는 몸이 허약하여, 하루동안 급변한 고도의 변화를 느끼면 어지러움과 함께, 구토를 하며 쓰러진다.

형석이는 이런 증상을 최소화하기 위해, 경로 중 가장 높은 지점과, 가장 낮은 지점의 고도차가 가장 작게 등산 경로를 정하려고 한다. 하지만 등산 준비로 바쁜 형석이는 당신에게 이 문제를 부탁하였다.

산은 N*N의 크기로 이루어져 있다. 형석이는 (1,1)을 시작점으로, (N,N)을 도착점으로 정하였다. 또한 형석이는 상, 하, 좌, 우의 인접한 칸으로 이동할 수 있다. 가능한 형석이의 등산 경로 중, 가장 높은 지점과 낮은 지점의 차가 최소가 되는 경우의 그 값을 구하여라.

시간제한: 1초

입력

첫째 줄에 N(2<=N<=100)이 주어진다. 다음 N개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

출력

첫째 줄에 경로 중 고도의 최대와 최소의 차가 가장 작아질 때의 그 값을 출력하세요.

힌트

parametric search & BFS(or A*)

소스

#include <stdio.h>

__inline int max(int a, int b) {

return a > b ? a : b;

}

__inline int min(int a, int b) {

return a < b ? a : b;

}

#define MAX 987654321

int main() {

int N;

scanf("%d", &N);

int map[101][101];

int min_v = MAX;

int max_v = 0;

for (int i = 1; i <= N; i++)

for (int j = 1; j <= N; j++) {

scanf("%d", &map[i][j]);

if (map[i][j] < min_v) min_v = map[i][j];

if (map[i][j] > max_v) max_v = map[i][j];

}

int s_max = max(map[1][1], map[N][N]); //시작과 끝중 큰값

int s_min = min(map[1][1], map[N][N]); //시작과 끝중 작은값

int queue[10001]; // BFS에 사용할 deque

int low, hi;

int top, bottom;

int audit;

int Ans = MAX;

for (bottom = min_v; bottom <= s_min; bottom++) //최소값의 범위 : min_v ~ s_min

{

low = s_max;

hi = max_v;

top = MAX;

while (low <= hi) // 각 lower bound에 대하여 s_max와 max_v사이의 p-search

{

int chk[101][101] = { 0 }; // 방문여부 확인

chk[1][1] = 1;

int s = 0;

int e = 1;

queue[0] = 1000 + 1;

audit = 0; // 끝점에 도달했는지 여부

int mid = (low + hi) >> 1;

while (s < e) // BFS (A*로하면 더 빠를듯)

{

int x = queue[s] / 1000;

int y = queue[s] % 1000;

s++;

if (x != 1 && chk[x - 1][y] == 0 && map[x - 1][y] <= mid && map[x - 1][y] >= bottom)

{

chk[x - 1][y] = 1;

queue[e] = (x - 1) * 1000 + y;

e++;

}

if (x != N && chk[x + 1][y] == 0 && map[x + 1][y] <= mid && map[x + 1][y] >= bottom)

{

if ((x + 1) == N && y == N) {

audit = 1;

break;

}

chk[x + 1][y] = 1;

queue[e] = (x + 1) * 1000 + y;

e++;

}

if (y != 1 && chk[x][y - 1] == 0 && map[x][y - 1] <= mid && map[x][y - 1] >= bottom)

{

chk[x][y - 1] = 1;

queue[e] = x * 1000 + y - 1;

e++;

}

if (y != N && chk[x][y + 1] == 0 && map[x][y + 1] <= mid && map[x][y + 1] >= bottom)

{

if (x == N && (y + 1) == N) {

audit = 1;

break;

}

chk[x][y + 1] = 1;

queue[e] = x * 1000 + y + 1;

e++;

}

}

if (audit == 1) {

hi = mid;

if (low == hi) {

top = hi;

break;

}

}

else low = mid + 1;

}

if (audit == 0) continue;

Ans = min(Ans, top - bottom);

}

printf("%d", Ans);

}

입력 예제

5
1 1 3 6 8
1 1 8 5 6
8 10 0 4 3
8 0 2 3 4
4 3 0 2 1

출력 예제

5

#8. 재밋는 게임

시간 제한	메모리 제한
2.0 초	512 MB

문제

형석이는 M*N 그리드 위에 놓여있는 MN개의 흰색과 검은색 돌들을 가지고 게임을 한다.

인접해 있는 같은 색의 돌들은 같은 그룹을 형성한다. 위를 보면 A~F의 6개의 그룹을 확인할 수 있다. 여기서 하나의 그룹을 뒤집게 되면, 그 그룹의 색이 반전된다. 아래의 사진은 A그룹을 뒤집었을 때의 그림이다. A라는 그룹을 뒤집었을 때, 인접한 다른 색의 그룹과 합쳐지는 것을 확인할 수 있다. (흰색 B그룹과 합쳐졌다.)

그 후, C를 뒤집게 되면, 아래와 같다. (마찬가지로, A,B,C,D가 한그룹이 되었다.)

그 다음 위에 있는 흰색그룹을 뒤집으면, 전체가 검은색으로 바뀐다. 이렇게 전체를 모두 같은 색으로 만드는 것이 목표이다.

문제는 위의 방법대로 진행하였을 때, 모든 바둑돌을 같은 색으로 만드는 최소한의 단계수를 구하는 것이다.

시간제한: 1초

입력

첫째 줄에는 M*N 그리드는 나타내는 두 양의 정수 M과 N이 빈칸을 사이에 두고 주어진다. M과 N은 2이상 100이하이다. 둘째 줄부터 M개의 각 줄에는 그리드의 가로줄 한 줄에 놓여진 흰색 동을 나타내는 0과 검은색 돌을 나타내는 1이 빈칸을 사이에 두고 연속해서 N개가 주어진다.

출력

첫째 줄에 모든 돌들이 같은 색이 되도록 하는 색 바꾸기의 최소 횟수를 출력한다.

힌트

입력 예제

5 6
1 1 0 1 0 0
1 0 0 1 1 1
1 1 0 1 1 1
0 0 0 0 0 0
1 1 1 0 1 1

출력 예제

2

힌트

Graph, 흰돌과 검은돌의 집합을 하나의 노드로 간주했을 때, 트리의 최장 길이를 구한다.