cdjs의 코딩 공부방

E 풀수 있을것 같은데? 아니 안되나? 으악!!

하고 터져버린 contest...

어차피 D까지는 거의 다 풀었겠지만 그래도 후기 쓰는 느낌으로 푼 문제들의 풀이를 해보도록 하자.

https://codeforces.com/contest/1335/problem/A

A. Candies and Two Sisters

문제가 무척이나 간단하고 쉬웠다.

숫자 n이 주어지고, 해당 n을 a>b (a>0, b>0, a+b=n)을 만족시키게 나누어 주는 경우의 수를 물어보는 문제였다.

경우를 두 가지로 나누어 보자.

1. n%2==0, 즉 n이 짝수일 때,

경우의 수는 정확히 n/2 - 1번이 나오게 된다. 가령 n이 6일 때, (5,1), (4,2)로 두 가지 경우가 존재한다.

2. n%2==0, 즉 n이 홀수일 때

경우의 수는 정확히 n/2번 나오게 된다. 가령 n이 7일 때, (6,1), (5,2), (4,3)으로 세 가지 경우가 존재한다.

이를 식 하나로 정리하면,

ans = (n-1)/2 로 정리할 수 있다.

그래서 그냥 n을 입력 받아서 (n-1)/2를 출력하면 되는 문제였다.

https://codeforces.com/contest/1335/problem/B

B. Construct the String

n, a, b를 입력받아서 크기 a의 substring에서 정확히 b개의 distinct한 글자가 들어가게 string을 만들어야 하는 문제였다.

풀이 방법이 여러 가지가 나올 수 있는 문제였다.

일단 내가 처음 생각해서 제출한 방법은 다음과 같았다.

1. 우선 크기 a-b+1만큼 모두 'a'로 채운다.

2. 그 뒤, b-1만큼 b,c,d,...으로 채운다.

3. 반복한다.

라는 생각으로 문제를 풀었다.

그런데 내 친구들이 푼걸 보니, 그냥 더 간단하게 처음부터 끝까지 b번만큼 abcdabcd...으로 반복하면 되더라...

어떻게 풀었건, 이런 방법들로 풀면 OK일것같다.

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

C. Two Teams Composing

한 쪽 팀에는 같은 능력치를 보유한 사람만, 다른 한 쪽 팀에는 서로 다른 능력치를 보유한 사람만으로 채울 때 최대 몇명까지 팀을 채울 수 있는지를 물어보는 문제였다. (양쪽 팀의 사람 수가 같다는 전제 하에)

어떻게 나눠야 최대 인원으로 팀을 나눌 수 있을지 생각해보자.

우선, 모두가 동일한 능력치를 가진 팀의 최대 인원은, 입력받은 숫자 중에 가장 자주 나온 숫자의 개수와 동일하다.

즉, 1 2 3 4 4 4 가 입력으로 주어지면 동일한 능력치 팀은 최대 3명이다.

모두가 다른 능력치를 가진 팀의 최대 인원은 반대로, 입력치의 서로 다른 숫자의 개수가 될 것이다.

즉, 1 2 3 4 4 4 가 입력으로 주어지면 서로 다른 능력치 팀은 최대 4명이다.

여기서 주의해야 할 점은, "서로 다른 숫자"에는 "가장 많은 개수의 숫자"도 포함된다는 것이다. 

자, 이제 서로 다른 숫자의 개수와 가장 자주 나온 숫자의 개수를 구한 뒤 어떻게 해야 할지 경우를 나눠보자.

1. 서로 다른 숫자의 개수 > 가장 많이 나온 숫자의 개수인 경우

ex) 1 2 3 4 5 5 5

이 경우, 최대로 많이 나눠도 가장 많이 나온 숫자의 개수 (5 5 5로 3개)까지만 팀이 나눠지므로, 가장 많이 나온 숫자의 개수가 정답이 된다.

2. 서로 다른 숫자의 개수 < 가장 많이 나온 숫자의 개수

ex) 1 2 3 3 3 3

이 경우, (1, 2, 3), (3, 3, 3)으로 나눌 수 있으니, 서로 다른 숫자의 개수가 정답이 된다.

3. 서로 다른 숫자의 개수 == 가장 많이 나온 숫자의 개수인 경우

ex) 1 2 3 3 3

이 경우, (1, 2), (3, 3)으로 최대 2명까지만 나눌 수 있으니, 서로 다른 숫자의 개수 - 1 이 정답이 된다.

이렇게 경우의 수를 세 가지로 나누면 손쉽게 정답을 구할 수 있다.

참고로, "서로 다른 숫자의 개수"에 "가장 많이 나온 숫자"를 포함하지 않으면 문제를 풀기 무척 까다로워 진다.

가령, 입력이 1,2,3,3,3,3으로 주어진 경우, 분명 서로 다른 숫자와 가장 많이 나온 숫자의 개수는 각가 2,4이지만 정답은 3이 되야 하기 때문이다.

https://codeforces.com/contest/1335/problem/D

D. Anti-Sudoku

솔직히 C보다 쉬운것 같은데;;

완성된 스도쿠를 최대 9개의 숫자를 바꿔서 각 줄과 블럭에 두 개 이상의 숫자가 겹치게 해야 한다.

일단, 각 블럭과 각 줄에 딱 하나씩만 죄다 숫자를 바꿔보자.

일단 나는, 저렇게 동그라미 친 부분의 숫자를 바꾸도록 했다.

해당 a[i][j]를  a[i][j]%9+1로 바꾸면 무조건 다른 숫자로 바뀌게 된다.

또한, 이렇게 하면 모든 줄, 블럭에 각각 숫자가 하나씩 바뀌므로 무조건 안티-스도쿠가 완성된다.

근데 다른 사람 코드 보다가 알았는데, 이렇게 할 필요도 없이 그냥 모든 숫자 '1'을 '2'로 바꾸면 완벽하게 해결되더라;

똑똑한 사람은 참 많은 것 같다.

딱 이렇게 40분컷 내고 장렬히 전사하고 말았다.

사실 E1을 풀 작정으로 1시간 20분동안 달렸으면 풀 수 있을만 했는데,

E2를 풀 작정으로 생각을 해버려서 그만...

E1 풀었으면 블루 갈만도 했는데 ㅠㅠ

사실 끝나고 나서 다른 문제들도 조금 풀긴 했는데, 에디토리얼 보고 푼거라 풀이로 울리긴 좀 그렇다 ㅎ;