코드포스 소개
코드포스는 온라인으로 프로그래밍 대회를 참여할 수 있는 웹사이트입니다. 대회는 2~3일에 한번 꼴로 빈번하게 열리고 참가자 수가 10000명이 넘어서 자신의 알고리즘 문제풀이 실력을 객관적으로 측정해보기에 좋을 듯 합니다. 비록 UI/UX는 현대적 사이트라 보기 힘들 정도로 구리지만 기능상에 문제는 없는 것 같네요?
코드포스 링크
아쉬움
코드포스를 이전에 두번 참가해봤는데 너무 어려워서 못푸는 문제가 많았어요. 그래서 이번에는 팀프로젝트처럼 소스코드와 로직을 공유하면서 친구들과 문제를 풀어보기로 했습니다. 하지만 이번에도 2시간 반동안 하나밖에 못풀어버렸네요? 그래도 이 문제는 충분히 풀만한데 너무 복잡하게 생각해서 코드조차 써보지 못했기에 아쉬움이 남아 정리해봅니다.
문제 보러가기!(원문)
문제 해석
문제 이름: 합성수 색칠하기
합성수는 1이 아닌 두 자연수의 곱으로 나타낼 수 있는 자연수이다. 즉 소수가 아닌 수이다.
합성수의 예: 6, 4, 120, 27
합성수가 아닌 수의 예: 1, 2, 3, 17, 97
n개의 합성수가 주어진다. 주어지는 합성수를 a1, a2, ... , an이라 하자. 각각의 합성수들을 m개의 색깔로 색칠하려 한다. (1 <= m <= 11) 그리고 다음의 조건에 따라 색칠한다.
- 임의의 i,j에 대하여 gcd(ai, aj) > 1 (i != j)이면 같은 색으로 칠할 수 있다. (gcd 함수는 두 수의 최대공약수를 반환합니다.) 즉, ai와 aj가 서로소이면 같은 색으로 칠할 수 있다.
- 각각의 합성수들은 항상 색칠되어야 하며 한가지 색깔로 칠해진다.
- 1부터 m까지의 색깔에 대하여 각각의 색깔을 가진 합성수가 적어도 하나 존재해야 한다.
입력값
- 첫번째 줄에 테스트 케이스의 개수 t (1 <= t <= 1000)
- 각각의 테스트 케이스에 대하여 합성수의 개수 n (1 <= n <= 1000)가 주어지고, 그 다음 줄에 합성수 a1, a2, ..., an이 주어진다. (4 <= ai <= 1000)
출력값
각각의 테스트 케이스에 대하여 두 줄을 출력한다. 첫번째 줄은 색깔의 개수 m, 두번째 줄은 각각의 원소가 칠해지는 색깔을 출력한다.
예시
- 입력
3
3
6 10 15
2
4 9
23
437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961- 출력
1
1 1 1
2
2 1
11
4 7 8 10 7 3 10 7 7 8 3 1 1 5 5 9 2 2 3 3 4 11 6풀이과정 보기
모든 합성수는 그것의 제곱근보다 크지 않은 소인수를 적어도 하나 가집니다. 증명은 주제에서 멀어지기에 생략하겠습니다. 문제에서 합성수는 1000 이하라고 했으므로 √1000 = ~31.6, 즉 32 이하의 소인수를 가집니다. 2부터 32 사이의 소수의 개수는 11개입니다. m <= 11이 문제에서 주어졌으므로 이 11가지의 소수를 각각의 색깔로 사용한다면 입력되는 모든 합성수를 칠할 수 있습니다. 따라서 다음과 같이 풀이과정을 작성할 수 있습니다.
1. 합성수의 개수만큼의 0을 저장하는 배열 arr을 생성한다.
2. 모든 합성수가 2로 나누어 떨어지는지 확인하고 나누어 떨어지면 arr[해당 합성수] = 1로 바꾼다.
3. 합성수가 3로 나누어 떨어지는지 확인하고 나누어 떨어지면 arr[해당 합성수] = 2로 바꾼다.
4. 31보다 작은 다른 소수에 대하여 (2), (3)의 과정을 동일하게 반복한다.
3. 합성수가 31로 나누어 떨어지는지 확인하고 나누어 떨어지면 arr[해당 합성수] = 11로 바꾼다.
4. arr 배열을 출력한다.
소스코드는 추후에 게시하겠습니다. 과제랑 자격증 공부가 끝난 뒤에...
참고 - 소수 목록 보기
참고 - 모든 합성수는 그것의 제곱근보다 크지 않은 소인수를 적어도 하나 가진다의 증명
