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*k + r 꼴일때, r이 3의 배수가 아니라면 n = 5*(k-1) + (r+5) 으로 변형해서 나머지항이 3의 배수가 될 때까지 반복한다는것과 동치이다. 만약 숫자가 충분히 크지 않다면 나머지가 3의 배수가 되지 않아서 불가능한 상황이 생길 수 있음에 유의하자.

 

 

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

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

세 변의 길이 i, j, k에 대해 i <= j <= 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로만 이루어진 숫자이다. 이 숫자의 길이에 따라 케이스가 나뉜다.

i). 숫자의 길이가 짝수이다.

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

ii). 숫자의 길이가 홀수이다.

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