[코드포스] Codeforces Round #634 (Div. 3)

대회 링크: http://codeforces.com/contest/1335

A번 문제: http://codeforces.com/contest/1335/problem/A

 

  n개의 사탕을 두 사람이 나눠야 한다. 두 사람이 가지는 사탕의 수를 각각 a와 b라고 하자. 이 때 a > 0, b > 0, a > b가 되도록 하는 경우의 수를 출력하는 문제다.

 

[ 문제 해설 ]

 

  예를 들어, 다음과 같은 n들을 고려해보자.

 

  n = 1일 때는 조건에 맞게 나눌 수 있는 경우가 없다.

  n = 2일 때는 조건에 맞게 나눌 수 있는 경우가 없다.

  n = 3일 때는 (2, 1)로 나눌 수 있으므로 경우의 수는 1이다.

  n = 4일 때는 (3, 1)로 나눌 수 있으므로 경우의 수는 1이다.

  n = 5일 때는 (3, 2), (4, 1)로 나눌 수 있으므로 경우의 수는 2다.

  n = 6일 때는 (4, 2), (5, 1)로 나눌 수 있으므로 경우의 수는 2다.

  n = 7일 때는 (4, 3), (5, 2), (6, 1)로 나눌 수 있으므로 경우의 수는 3이다.

 

  결과적으로 경우의 수는 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, ... 순으로 나열되는 것을 알 수 있다. 따라서 단순히 (n - 1)를 2로 나눈 몫을 출력하면 그것이 정답이다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    print((n - 1) // 2)

 

B번 문제: http://codeforces.com/contest/1335/problem/B

 

  길이가 n인 문자열 s를 만드는데, 길이가 a인 모든 부분 문자열들이 b개의 서로 다른 문자들로 구성되도록 하는 문제다. 조건만 만족한다면 길이가 n인 문자열 s를 아무거나 출력해도 된다.

 

  예를 들어 n = 7, a = 5, b = 3일 때를 고려해보자. 이 때는 tleelte가 정답이 될 수 있다.

 

[ 문제 해설 ]

 

  이 문제는 길이가 a인 부분 문자열 k를 만들어서 순환적으로 출력하면 된다. n = 7, a = 5, b = 3일 때를 생각해보자.

 

  k = ['a', 'b', 'c', 'a', 'a']로 만들게 되면, 예를 순환적으로 출력하면 다음과 같다.

 

  {'a', 'b', 'c', 'a', 'a', 'a', 'b', 'c', 'a', 'a', 'a', 'b', 'c', 'a', 'a', ...}

 

  이렇게 되면, 길이가 5인 어떤 부분 문자열도 3개의 서로 다른 문자로 구성된다. 즉, 문제 해결의 아이디어는 앞에서부터 b만큼은 'a'부터 시작해 차례대로 문자를 담고, 나머지는 그냥 'a'만 나열하도록 문자열 k를 만든다. 이후에 k를 순환적으로 출력하면 정답이다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n, a, b = map(int, input().split())
    k = []
    
    # 앞의 b만큼은 'a'부터 시작해 차례대로 문자를 담기
    for i in range(b):
        k.append(chr(ord('a') + i))
    # 나머지는 그냥 'a'만 나열하도록 문자를 담기
    for i in range(a - b):
        k.append('a')
  
    # 이제 문자열 k를 순환적으로 출력하면 정답
    for i in range(n):
        print(k[i % a], end='')
    print()

 

C번 문제: http://codeforces.com/contest/1335/problem/C

 

  n명의 학생을 두 팀으로 나눌 때, 첫 번째 팀은 모두 스킬이 다르고 두 번째 팀은 모두 스킬이 같도록 구성하고자 한다. 단, 두 팀의 인원이 동일해야 한다. 이 때 팀의 가능한 최대 인원 수를 찾는 문제다.

 

  예를 들어 n = 7이고, 학생들의 스킬이 {4, 2, 4, 1, 4, 3, 4}라면 다음과 같이 나누었을 때 각 팀의 인원수가 제일 많다.

 

  첫 번째 팀: {1, 2, 3}

  두 번째 팀: {4, 4, 4}

 

  이 때 팀의 인원수는 3이다.

 

[ 문제 해설 ]

 

  이 문제는 각 스킬의 번호마다 등장 횟수를 체크(count_map)하고, 스킬의 번호가 총 몇 개 있는지 체크(distinct_count)하여 해결할 수 있다.

 

  예를 들어 위의 예시에서는 각 스킬의 번호마다 등장 횟수가 다음과 같다.

 

  1번 스킬: 1명

  2번 스킬: 1명

  3번 스킬: 1명

  4번 스킬: 3명

 

  또한 전체 스킬의 번호가 총 4개가 된다.

 

  이제 각 스킬 번호에 대해서, 그 스킬을 가진 학생들만을 오른쪽 팀에 두는 경우들을 고려하면 된다. 다만, 한 명의 학생은 왼쪽 팀에 넘겨 주어도 괜찮다. 이를 이용해 정답 코드를 작성할 수 있다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    result = 0

    count_map = {}
    distinct_count = 0
    for i in data:
        if i not in count_map:
            count_map[i] = 1
            distinct_count += 1
        else:
            count_map[i] += 1
  
    # 각 스킬 번호를 확인하며
    for (key, value) in count_map.items():
        # 해당 스킬을 가진 학생을 두 번째 팀에 두는 경우를 고려하여, 최대 인원 수 찾기
        now = max(min(count_map[key], distinct_count - 1), min(count_map[key] - 1, distinct_count))
        result = max(result, now)
    print(result)

 

D번 문제: http://codeforces.com/contest/1335/problem/D

 

  이 문제는 전형적인 스도쿠 퍼즐이 무엇인지 알아야 한다. 다음과 같이 이미 완성된 스도쿠 보드가 있다고 해보자.

 

 

  이 때 안티 스도쿠란, 다음의 조건을 만족하는 보드를 말한다.

 

  1) 각 행에 대하여 최소한 두 개의 원소가 같아야 한다.

  2) 각 열에 대하여 최소한 두 개의 원소가 같아야 한다.

  3) 모든 3 x 3 블럭(Block)에서 최소한 두 개의 원소가 같아야 한다.

 

  이번 문제는 완성된 스도쿠 보드가 입력되었을 때, 안티 스도쿠를 만들어 출력하는 문제다.

 

[ 문제 해설 ]

 

  깊게 고민하면 문제 해결 아이디어를 떠올릴 수 있다. 다양한 방법이 있을 수 있겠지만, 저자는 다음과 같이 풀었다. 바로 다음의 9가지 위치에 있는 원소들의 값을 기존의 값이 아닌 다른 아무 값으로나 바꾸면 된다.

 

 

  따라서 9개의 칸에 있는 각 원소의 값이 1인 경우에는 2로 바꾸고, 1이 아닌 경우에는 1로 바꾸면 된다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    data = []
    for i in range(9):
        data.append(list(map(int, input())))

    # 9가지 위치의 값을 기존의 값이 아닌 다른 값으로 변경
    data[0][0] = 2 if data[0][0] == 1 else 1
    data[1][3] = 2 if data[1][3] == 1 else 1
    data[2][6] = 2 if data[2][6] == 1 else 1
    data[3][1] = 2 if data[3][1] == 1 else 1
    data[4][4] = 2 if data[4][4] == 1 else 1
    data[5][7] = 2 if data[5][7] == 1 else 1
    data[6][2] = 2 if data[6][2] == 1 else 1
    data[7][5] = 2 if data[7][5] == 1 else 1
    data[8][8] = 2 if data[8][8] == 1 else 1
  
    for i in range(9):
        print(''.join(map(str, data[i])))