백준 및 코드포스

n, k, r, c를 입력받고, r행 c열에는 X가 무조건 있다고 할 때, n x n의 배열의 한 점에서 가로 세로 k개 안에 X가 최소로 있어야합니다.

3 3 3 2 를 입력받았을 때 아래와 같은 경우의 수가 있겠죠.

그냥 constructive 하고 빠르게 생각나는대로 짰습니다.

#include <stdio.h>
int main() {
int n, k, r, c, t;
int arr[1003][1003] = {};
scanf("%d", &t);
while(t--) {
    scanf("%d%d%d%d", &n, &k, &r, &c);
    r %= k;
    c %= k;
    for(int q = 0; q <= n; q++) {
        for(int i = r + q; i <= n + k; i+=k) {
            for(int j = c + q; j <= n + k; j+= k) {
                arr[i][j] = 1;
            }
        }
    }
    for(int i = k; i < n + k; i++) {
        for(int j = k; j < n + k; j++) {
            if(arr[i][j] == 1) printf("X");
            else printf(".");
        }   
        printf("\n");
    }
    for(int i = 0; i <= n + k; i++) {
        for(int j = 0; j <= n + k; j++) {
            arr[i][j] = 0;
        }
    }
}
}

https://codeforces.com/contest/1706/problem/C

두 가지 경우로 나눠서 그리디하게 풀 수 있습니다.

1. 현재 꽂혀있는 플러그 중 나중에 쓰이지 않는 플러그가 있는 경우, 그 플러그를 뽑고 새로운 플러그를 꽂아주면 됩니다.

2. 현재 꽂혀있는 플러그 전부 나중에 쓰일 일이 있다면, 제일 등장 순서가 늦은 플러그를 뽑아주면 됩니다. 

밑에 자세히 설명해두었습니다.

ex) 

2 7

2 3 1 2 3 2 2 의 경우

2 3 플러그를 먼저 꽂은 후, 1을 꽂기 위해서 하나를 뽑아야 하는데, 그 뒤의 플러그 등장 순서를 보면 2 -> 3으로 3이 현재 꽂혀있는 플러그 중 등장순서가 가장 늦기 때문에 3번 플러그를 뽑아주면 됩니다.

생각하기도 쉽고, 반례도 딱히 없는 문제이지만 구현이 힘들었습니다.

반례 

2 7

2 3 1 2 3 2 2

OUTPUT : 2

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int main() {
int count = 0, c = 0,temp = -1, n, m, check[1000] = {}, arr[1000] = {}, plug[1000] = {}, index[1000] = {};
bool already = 0;
scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d", &arr[i]);
    }
        for(int j = 0; j < m; j++) {
            if(plug[arr[j]] == 1) continue;
            else {
                plug[arr[j]] = 1;
                count++;
            }
            if(count == n) {
                temp = j;
                break;
            }
        }
    int later, none;
    for(int i = temp + 1; i < m; i++) {
        int zero = 0;
        for(int j = 0; j <= m; j++) {
            check[j] = 0;
            index[j] = 0;
        }
        later = 0, none = 0;
        already = 0;
        if(plug[arr[i]]) {
            already = 1;
        }
        if(already == 0) {
            for(int j = i + 1; j < m; j++) {
                if(plug[arr[j]] == 1) {
                    later = arr[j];
                    if(index[arr[j]] == 0) {
                        index[arr[j]] = ++zero;
                    }
                }  
                if(check[arr[j]] == 0 && plug[arr[j]] == 1) {
                    check[arr[j]] = 1;
                }
            }
            for(int j = 0; j < m; j++) {
                if(plug[arr[j]] == 1 && check[arr[j]] == 0) {
                    none = arr[j];
                    break;
                }
            }
            if(none) {
                c++;
                plug[none] = 0;
                plug[arr[i]] = 1;
            }
            else if(later) {
                for(int j = 0; j <= m; j++) {
                    if(index[j] == zero) {
                        later = j;
                        break;
                    }
                }
                c++;
                plug[later] = 0;
                plug[arr[i]] = 1;
            }
        }
       
    }
    printf("%d", c);
}

비둘기집 원리를 사용하는 문제입니다.

k가 최대 10만이라는 점을 이용하여 k로 무언가를 나눈 나머지의 종류는 0~99999의 10만가지 라는 점을 이용합니다.

풀이 : N을 적어가며 K로 나누면서 나온 나머지의 값이 여태 나온 적이 있는지 배열로 저장해서 확인한 후, 똑같은 나머지가 나온 적이 있다면 숫자를 무한번 나눠도 loop에 빠지기 때문에 -1을 출력해주면 됩니다.

나머지가 0이 된다면 나누어 떨어진 것이기 때문에, 여태 N을 몇 번 썼는지 출력해주면 됩니다.

혹은 

N을 새로 적는 과정이 10만번 이상 반복될 경우 비둘기집 원리에 의해 겹치는 나머지가 1개 이상 발생하기 때문에, for문을 10만번 반복해보고 그래도 정답이 출력되지 않았을 경우 -1을 출력하는 방식으로 풀어도 가능합니다.

풀이 1

#include <stdio.h>
int main() {
    long long n, m, ans = 0;
    short arr[100001] = {};
    scanf("%lld %lld", &n, &m);
    int digit = 0, temp = n;
    while(n) {
        n /= 10;
        digit++;
    }
    n = temp;
    for(int i = 0; i <= 200000; i++) {
        while(n < m) { //while loop을 통해 N을 적어가는 과정
            for(int m = 0; m < digit; m++) {
                n *= 10;
            }
            ans++;
            n += temp;
        }
        n %= m;
        if(n == 0) { //나머지가 0인 경우 정답 출력
            printf("%lld", ans + 1);
            return 0;
        }
        else if(arr[n] == 0) { //처음 나온 나머지의 경우 나왔다고 체크해줍니다.
            arr[n]++;
        }
        else if(arr[n] > 0) { //여태 나온 나머지일 경우 -1 출력
            printf("-1");
            return 0;
        }
    }
}

풀이 2

#include <stdio.h>
int main() {
    long long n, m, ans = 0;
    scanf("%lld %lld", &n, &m);
    int digit = 0, temp = n;
    while(n) {
        n /= 10;
        digit++;
    }
    n = temp;
    for(int i = 0; i <= 100000; i++) {
        while(n < m) {
            for(int m = 0; m < digit; m++) {
                n *= 10;
            }
            ans++;
            n += temp;
        }
        n %= m;
        if(n == 0) {
            printf("%lld", ans + 1);
            return 0;
        }
    }
    printf("-1");
}

반례

10000000 9

Output : 9


10000000 99

Output : 99


10000000 9999

Output : 9999


10000000 99999

Output : 45


97859271 97517

Output : 20895


797859271 98710

Output : -1