KOTIP 2일차

#1. 막대기

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	801	115 (14%)	90

문제

n가지 종류의 막대기가 있다. 막대기의 길이는 모두 다르다. 이 막대기들을 적당히 사용해서, 총 길이가 K가 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 막대기는 여러번 사용할 수 있다.)

입력

첫째 줄에 n,k 가 주어진다. (1 <= n <= 100, 1 <= k <= 10,000) 다음 n개의 줄에는 각각의 막대기의 길이가 주어진다.

출력

첫째 줄에 경우의 수를 출력한다. 1000000으로 나눈 나머지를 출력하시오.

힌트

입력 예제

3 10
1
2
5

출력 예제

10

힌트

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

소스

#include <stdio.h>

 

int stick[101];

int d[10001][101];

int N, K;

int dp(int n, int order) {

    if (n == 0) return 1;

    int *ret = &d[n][order];

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

    *ret = 0;

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

    {

        if (n - stick[i] < 0) continue;

        *ret += dp(n - stick[i], i);

        *ret %= 1000000;

    }

    return *ret;

}

int main() {

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

    for (int i = 1; i <= N; i++) scanf("%d", &stick[i]);

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

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

            d[i][j] = -1;

    printf("%d",dp(K,1)% 1000000);

}

#2. 합분해

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	921	170 (18%)	146

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1≤N≤200), K(1≤K≤200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

입력 예제

20 2

출력 예제

21

힌트

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

소스

#include <stdio.h>

#define LL long long

#define MAX 1000000000

LL d[201][201]; //d[i] : i를 만드는 방법의 수

int N, K;

LL dp(int n, int order) {

    if (n == 0) return 1;

    if (order == 0) return 0;

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

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

    *ret = 0;

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

    {

        if (n - i < 0) break;

        *ret += dp(n - i, order - 1);

        *ret %= MAX;

    }

    return *ret;

}

int main() {

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

    printf("%lld", dp(N, K) % MAX);

}

#3. newnight

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	111	17 (15%)	12

문제

동현이는 카이스트 대표 체스 선수이다. 기존의 체스 게임이 너무 쉬운 나머지 새로운 체스 말을 만들려고 한다. 이 말을 new night라고 정의하자.

이 말은 자신의 위치에서 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위 이렇게 총 네 가지 위치로 갈 수 있다.

N*M 격자로 이루어진 맵과 장애물 (말을 놓을 수 없는 위치) 가 주어졌을 때, newnight을 최대로 많이 두고 싶어한다.

동현이는 최근에 술을 너무 많이 마셔 문제를 풀 수 없는 상태이다. 우리가 취한 동현이를 도와주자.

위 그림처럼 newnight는 자신의 위치에서 A,D,E,C를 갈 수 있다. “한 번의 이동” 으로 닿을 수 없게 newnight를 최대로 많이 두고 싶다.

입력

입력의 첫 줄에는 테스트케이스의 개수 C가 주어진다. 각각의 테스트 케이스는 아래와 같이 두 부분으로 이루어진다. (1<= C <= 1000)

첫 번째 부분에서는 맵의 세로길이 N과 가로길이 M이 한 줄에 주어진다. (1 ≤ M ≤ 10, 1 ≤ N ≤ 10)

두 번째 부분에서는 정확하게 N줄이 주어진다. 그리고 각 줄은 M개의 문자로 이루어져있다. 모든 문자는 ‘.’(놓을 수 있는 자리) 또는 ‘x’(놓을 수 없는 자리, 소문자)로 구성된다.

출력

각각의 테스트 케이스에 대해 맵에서 둘 수 있는 최대 newnight의 수를 출력한다.

입력 예제

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

출력 예제

4
1
2
46

힌트

비트마스크 다이나믹프로그래밍(Bitmask + DP)

소스

#include <stdio.h>

int N, M;

char map[12][12];

int d[101][8200];

__inline int max(int a, int b) {

    return a > b ? a : b;

}

int cnt, Ans;

int bitmask(int row, int col) {

    return map[row][col] == 'x' ? 1 : 0;

}

int dp(int num) {

    if (num > M*N) return 0;

    int row = ((num - 1) / M) + 1;

    int col = ((num - 1) % M) + 1;

    int bm = bitmask(row, col);

    int sft = 1;

    for (int i = col - 1; i > 0; i--)

    {

        bm += bitmask(row, i) << sft;

        sft++;

    }

    for (int i = col - 1; i <= M; i++)

    {

        bm += bitmask(row - 1, i) << sft;

        sft++;

    }

    int *ret = &d[num][bm];

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

    *ret = 0;

    //말 놓는경우

    if (map[row][col] == 'x') *ret = dp(num + 1);

    else {

        if (map[row][col - 1] == 'x' && map[row - 1][col - 1] == 'x' && map[row - 1][col + 1] == 'x')

        {

            char tmp = map[row][col + 1];

            map[row][col + 1] = 'x';

            *ret = 1 + dp(num + 1);

            map[row][col + 1] = tmp;

        }

        char tmp = map[row][col];

        map[row][col] = 'x';

        *ret = max(*ret, dp(num));

        map[row][col] = tmp;

    }

    return *ret;

}

int main() {

    int C;

    scanf("%d", &C);

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

    {

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

        for (int i = 1; i <= N; i++) scanf("%s", &map[i][1]);

        for (int i = 0; i <= N; i++) map[i][0] = map[i][M + 1] = 'x';

        for (int i = 0; i <= M; i++) {

            map[0][i] = map[N + 1][i] = 'x';

        }

        int len = 8;

        for (int i = 1; i <= M; i++, len <<= 1);

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

        {

            for (int k = 0; k <= len; k++) {

                d[j][k] = -1;

            }

        }

        printf("%d\n", dp(1));

    }

}

#4. 가장 많은 수

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	632	113 (18%)	89

문제

N개의 정수가 주어진다. 이 중 가장 많이 등장하는 수를 구하시오. 만약 이런 수가 여러 개라면 작은 수를 출력하세요.

시간제한: 1초

입력

첫째 줄에는 정수의 개수 N이 주어진다. (1<=N<=1000000)

둘째 줄부터 N개 줄에 정수가 주어진다. 이 수의 절대값은 2^31 - 1 이하이다.

출력

가장 많이 등장하는 정수를 출력하시오.

입력 예제

4
1
2
3
3

출력 예제

3

힌트

정렬(Sorting)

소스

#include <stdio.h>

 

int tree[1000002];

void q_sort(int low, int hi) {

    int i = low;

    int j = hi;

    int pivot = tree[(i + j) >> 1];

    while (i<=j)

    {

        while (tree[i] < pivot) i++;

        while (pivot < tree[j]) j--;

        if (i <= j) {

            int tmp = tree[i];

            tree[i] = tree[j];

            tree[j] = tmp;

            i++;

            j--;

        }

    }

    if (i < hi) q_sort(i, hi);

    if (low < j) q_sort(low, j);

}

int main() {

    int N;

    scanf("%d", &N);

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

        scanf("%d", tree + i);

    //q_sort

    q_sort(1, N);

    tree[N + 1] = -987654321;

    int cnt = 1;

    int Ans_num=0;

    int Ans_cnt=0;

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

    {

        if (tree[i] == tree[i - 1]) cnt++;

        else

        {

            if (Ans_cnt < cnt) {

                Ans_cnt = cnt;

                Ans_num = tree[i - 1];

            }

            cnt = 1;

        }

    }

    printf("%d", Ans_num);

}

5. 지은이가 지은 집

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	1015	90 (9%)	66

문제

최근에 지은이는 건축에 관심이 많아 집을 짓게 되었다. 태양이는 지은이가 지은 집에 놀러갔다. 근데 아니나 다를까 집에 작은 구멍이 있는 것이다. 지은이와 태양이는 집을 보수하기로 했다.

다행히도 지은이가 집을 짓다가 남은 재료가 남아서, 이를 이용하여 집을 보수하기로 했다. 구멍이 난 곳의 너비는 x센티미터이다. 태양이와 지은이는 사이가 너무 좋아서, 남은 재료 중 하나씩 골라서 이어 붙이고, 이로 구멍을 막기로 했다. 즉, 태양이과 지은이가 고른 재료의 길이가 L1, L2이면, L1+L2가 x와 같아야 구멍을 막을 수 있다. 크기가 다르면, 또 망가질 위험이 있기 때문이다.

그럼 이제 구멍을 완벽하게 막을 수 있는 두 막대를 구하는 프로그램을 작성하시오.

시간제한: 2초

입력

첫째 줄에는 구멍의 너비 x가 주어진다. X의 단위는 센티미터이다.

다음 줄에는 재료의 개수 n이 주어진다. (1<=n<=1000000)

다음 n개의 줄에는 재료의 길이 L이 주어진다. L의 단위는 나노미터이다. 재료의 길이는 10센티미터(100000000 나노미터)를 넘지 않는다.

출력

구멍을 완벽하게 막을 수 있는 두 조각이 없다면 ‘danger’를 줄력한다. 막을 수 있는 경우에는 ‘yes L1 L2’를 출력한다. (L1<=L2). 정답이 여러 개인 경우에는 |L1-L2|가 가장 큰 것을 출력한다.

입력 예제

1
4
9999998
1
2
9999999

출력 예제

yes 1 9999999

힌트

정렬(Sorting)

소스

#include <stdio.h>

#define MAX 987654321

int num[1000001];

int tree[1000001];

 

void swap(int n, int m) {

    int tmp = tree[n];

    tree[n] = tree[m];

    tree[m] = tmp;

}

int main() {

    int N, n;

    scanf("%d", &n);

    n *= 10000000;

    scanf("%d", &N);

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

    {

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

    }

    //build (min) heap tree(bottom-up)

    tree[N + 1] = MAX;

    for (int i = N / 2; i >= 1; i--)

    {

        int m = i;

        while (m <= N / 2)

        {

            if (tree[m] > tree[m << 1])

            {

                if (tree[m << 1] > tree[(m << 1) + 1])

                {

                    swap(m, (m << 1) + 1);

                    m = m * 2 + 1;

                }

                else

                {

                    swap(m, m << 1);

                    m <<= 1;

                }

            }

            else if (tree[m] > tree[(m << 1) + 1]) {

                swap(m, (m << 1) + 1);

                m = m * 2 + 1;

            }

            else break;

        }

    }

    //sorting num using heap tree

    int M = N;

    int idx = 1;

    while (M)

    {

        num[idx] = tree[1];

        tree[1] = tree[M];

        M--;

        idx++;

        int m = 1;

        while (m <= M / 2)

        {

            if (tree[m] > tree[m << 1])

            {

                if (tree[m << 1] > tree[(m << 1) + 1])

                {

                    swap(m, (m << 1) + 1);

                    m = m * 2 + 1;

                }

                else

                {

                    swap(m, m << 1);

                    m <<= 1;

                }

            }

            else if (tree[m] > tree[(m << 1) + 1]) {

                swap(m, (m << 1) + 1);

                m = m * 2 + 1;

            }

            else break;

        }

    }

    idx = 1;

    for (int i = N; i > idx; i--)

    {

        if (num[idx] + num[i] == n) {

            printf("yes %d %d", num[idx], num[i]);

            return 0;

        }

        else if (num[idx] + num[i] < n) {

            idx++;

            i++;

        }

    }

    printf("danger");

}

6. 집합

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	311	44 (14%)	35

문제

집합 A와 B에 각각 N, M개의 자연수가 들어있다. 이제 다음의 행동을 min(N, M)번 시행할 것이다.

• 집합 A, B에서 각각 자연수 하나씩 고르고, 고른 수는 각 집합에서 삭제한다
• 고른 두 수의 차를 집합 C에 넣는다.

우리의 목표는 집합 C에 있는 원소의 합을 최소로 하는 것이다.

시간제한: 1초

입력

첫째 줄에 N, M(1<=N, M<=1,000)이 주어진다. 다음 줄에는 집합 A의 원소, N개가 입력된다. 다음 줄에는 집합 B의 원소, M개가 입력된다. 각 원소는 1,000,000이하의 자연수이다.

출력

첫째 줄에 집합 C의 원소합의 최소를 출력한다.

입력 예제

2 1
10 20
30

출력 예제

10

7. 개구리

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	317	18 (6%)	15

문제

2차원 평면의 호수에 개구리 한 마리가 있다. 개구리는 호수위에 떠있는 연꽃들 사이를 돌아다니고 있다. 개구리는 총 4가지 방향으로 이동이 가능하다. 현재 위치인, (x, y)에서 임의의 양의 정수 d에 대하여,

A. (x+d, y+d)로 이동.
B. (x+d, y-d)로 이동.
C. (x-d, y+d)로 이동.
D. (x-d, y-d)로 이동.

가능하다.

개구리는 네 방향 중 한가지를 골라서, 그 방향에 있는 가장 가까운 연꽃으로 이동한다. 만약 연꽃이 없다면 제자리에 있는다. 그리고 개구리가 이동한 다음에, 원래 연꽃은 가라앉는다.

연꽃의 위치와, 개구리의 이동방향이 주어졌을 때, 개구리의 최종 위치를 출력하시오.

시간제한: 1초

입력

첫째 줄에 연꽃의 수 N과 점프의 수 K가 주어진다. (1<=N<=K<=100,000)

둘째 줄에는 개구리가 고른 방향 K개가 주어진다. 이 방향은 ‘A’, ‘B’, ‘C’, ‘D’로만 이루어져 있다.

셋째 줄부터 N개 줄에 걸쳐서 연꽃의 좌표 x, y가 주어진다. (0<=x, y<=1,000,000,000) 개구리는 처음 주어지는 연꽃위에 있다.

출력

개구리의 점프가 끝났을 때, 개구리의 좌표를 출력한다.

힌트

입력 예제

7 5
ACDBB
5 6
8 9
4 13
1 10
7 4
10 9
3 7

출력 예제

7 4

8. K번째 수

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	442	54 (12%)	45

문제

N개의 수가 입력되면, K번째로 작은 수를 출력한다.

시간제한: 2초

입력

첫째 줄에 N(1<=N<=5,000,000)과 K(1<=K<=N)이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐서 N개의 정수가 주어진다. (-10^9 <= 정수 <= 10^9)

출력

N개의 정수를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

입력 예제

2 1
1 
2

출력 예제

1

힌트

정렬(Sorting)

소스

#include <stdio.h>

#define MAX 1000000010

int num[5000010];

 

void swap(int n, int m) {

    int tmp = num[n];

    num[n] = num[m];

    num[m] = tmp;

}

int main() {

    int N, K;

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

    int idx = 1;

    int pivot;

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

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

    //build heap tree;

    num[N + 1] = MAX;

    for (int i = N >> 1; i >= 1; i--)

    {

        int m = i;

        while (m <= N >> 1)

        {

            if (num[m] > num[m << 1]) {

                if (num[m << 1] > num[(m << 1) + 1]) {

                    swap(m, (m << 1) + 1);

                    m = (m << 1) + 1;

                }

                else

                {

                    swap(m, m << 1);

                    m <<= 1;

                }

            }

            else if (num[m] > num[(m << 1) + 1]) {

                swap(m, (m << 1) + 1);

                m = (m << 1) + 1;

            }

            else break;

        }

    }

    //k times popping number

    int Ans;

    while (K)

    {

        Ans = num[1];

        num[1] = num[N];

        N--;

        K--;

        int m = 1;

        while (m <= N >> 1)

        {

            if (num[m] > num[m << 1]) {

                if (num[m << 1] > num[(m << 1) + 1]) {

                    swap(m, (m << 1) + 1);

                    m = (m << 1) + 1;

                }

                else

                {

                    swap(m, m << 1);

                    m <<= 1;

                }

            }

            else if (num[m] > num[(m << 1) + 1]) {

                swap(m, (m << 1) + 1);

                m = (m << 1) + 1;

            }

            else break;

        }

    }

    printf("%d", Ans);

}