KSHS 백준 동아리 입단 테스트 해설

백준 동아리를 만들며 인원이 많아 입단 테스트도 진행하게 되었다.

입단 테스트 자체는 브~골 셋으로만 구성되었지만, 친구들을 위해 풀이를 남긴다.

A번 - BOJ 15727 조별과제를 하려는데 조장이 사라졌다, 브5#

성우가 민건이를 최대한 빨리 찾으려면, 최대한 먼 거리를 이동해야 한다. 따라서 생각할 필요도 없이 1~5 중에 항상 5만큼의 거리를 이동해야 한다. 입력으로 주어진 거리를 5로 나누면 몇 번 움직여야 할지 알 수 있고, 이동횟수는 자연수이기 때문에 입력을 5로 나눈 값을 올림한 게 정답이 된다.

B번 - BOJ 31432 소수가 아닌 수 3, 브1#

어떤 수가 주어져도 항상 가능하다. 0~9까지 중 아무 숫자에 111을 곱해주면, 만들어진 수들은 모두 소수가 아님이 자명하기 때문이다. 또한 동시에, 이렇게 만들어진 수는 기존 숫자 외에 다른 숫자를 사용하지 않는다. 따라서 주어진 숫자 중 아무거나 하나를 골라서 111을 곱한 값을 출력하면 된다.

C번 - BOJ 2839 설탕 배달, 실4#

그리디, DP 등 다양한 방법으로 풀 수 있다. 최대한 적은 봉지를 들고 가려면, 5킬로그램 봉지 3개와 3킬로그램 봉지 5개 중에서 5킬로그램 봉지 3개를 택해야 할 것이다. 이를 기반으로, 설탕 무게를 5로 나눠서, 남은 나머지가 3의 배수라면 그때가 봉지의 최소 개수를 만드는 상황이다. 그렇지 않다면, 나머지에 5씩 더해가면서 3의 배수가 될 때까지 반복해주면 된다. 설탕 무게 $n = 5 \times k + r$ 꼴일 때, $r$이 3의 배수가 아니라면 $n = 5 \times (k - 1) + (r + 5)$로 변형해서 나머지항이 3의 배수가 될 때까지 반복한다는 것과 동치이다. 만약 숫자가 충분히 크지 않다면 나머지가 3의 배수가 되지 않아서 불가능한 상황이 생길 수 있음에 유의하자.

D번 - BOJ 2622 삼각형 만들기, 실5#

주어진 입력값을 $n$이라고 하자. 두 변의 길이가 주어지면 나머지 한 변의 길이는 $n$에서 두 변의 길이를 뺀 값으로 정해지기 때문에, 두 변의 길이로 가능한 조합을 전부 해볼 수도 있다. 하지만 이러면 시간초과가 생기기 때문에, 이를 줄일 방법을 생각해야 한다.

세 변의 길이 $i$, $j$, $k$에 대해 $i \le j \le k$라면 $i + j > k$를 만족해야 삼각형이 된다는 걸 이용하면 된다. $i$, $j$로 이중 반복문을 돌리되, $i$, $j$, $n - i - j$ 중 어떠한 값이라도 $n / 2$를 넘어가면 $i + j > k$를 만족할 수 없기 때문에 바로 break해주면 된다. 반복문 조건을 잘 설정해야 중복 없이 셀 수 있다.

E번 - BOJ 33615 1과 5, 골5#

3으로 나눈 나머지에 따라 케이스를 분류해서 풀 수 있다. 핵심은 3의 배수판정법이다.

3의 배수판정법: 어떤 수와, 그 수의 각 자릿수의 합은 3으로 나눈 나머지가 같다.

I. 3으로 나눈 나머지가 0#

이미 3의 배수이기 때문에 합성수이다. 더 이상 다른 숫자를 지울 필요 없이 '0 3'을 출력하면 된다.

II. 3으로 나눈 나머지가 1#

1. 수가 1을 포함하고 있다

   그 1을 지워주면 남은 숫자는 3의 배수가 된다. 3의 배수판정법을 참고하자.

2. 수가 1을 포함하지 않고 있다

   이 수는 5로만 이루어진 숫자이기 때문에, 아무것도 지우지 않아도 항상 5의 배수이다. '0 5'를 출력하면 된다.

III. 3으로 나눈 나머지가 2#

1. 수가 5를 포함하고 있다

   그 5를 지워주면 남은 숫자는 3의 배수가 된다. 3의 배수판정법을 참고하자.

2. 수가 5를 포함하지 않는다

   이 수는 1로만 이루어진 숫자이다. 이 숫자의 길이에 따라 케이스가 나뉜다.

   1. 숫자의 길이가 짝수이다

      이 수는 항상 11로 나누어떨어진다. 1111은 $11 \times 101$, 111111은 $11 \times 10101$ ... 이런 규칙으로 말이다. '0 11'을 출력하면 된다.

   2. 숫자의 길이가 홀수이다

      1을 1개만 지워주면 숫자의 길이가 홀수에서 짝수가 된다. '1 11'을 출력하면 된다.