백준 20311 화학 실헙

문제 설명

이번 문제는 시험관의 전체 개수, 시험관에 들어있는 시약 종류의 개수와 각 시약이 들어있는 시험관의 개수가 주어지고, 시험관을 나열할 때 모든 이웃한 시험관 쌍에 대해, 두 시험관에 들어 있는 시약의 색깔이 서로 다르게 나열할 수 있는 방법을 출력하는 문제입니다.

(조건을 만족하는 시험관 배열을 만들 수 있으면, 시험관의 색깔 번호를 공백으로 구분하여 순서대로 출력합니다. 답이 여러 개일 경우 아무거나 출력, 조건을 만족하는 시험관 배열을 만들 수 없으면 -1을 출력합니다.)

 

문제 풀이

아이디어

조건을 만족하는 방법

이웃한 두 시험관의 색이 무조건 다를 수 있는 조건 중 하나는 가장 많은 시약의 개수가 전체 시험관 개수의 절반을 넘어서면 안 되는 것입니다.

 

1.

가장 많은 시약의 수가 절반 이하라면, 0번째, 2번째, 4번째 .... 이런 식으로 한 개씩 비어있게 배치한다면 조건을 만족할 수 있습니다. (나머지 시약 또 우선 짝수 번째 인덱스를 끝까지 채운뒤 홀수 인덱스를 채워주면 됩니다.)

 

2.

가장 많은 시약의 수가 절반 이상이라면 어떻게 시험관을 배치하더라도 조건을 만족할 수 없습니다.

예) 총 개수 6개, 시약 a의 개수가 4개일 경우

a시약을 어떻게 배치하더라도 조건을 만족할 수 없음을 알 수 있습니다.

a a a b a c , a b a a c a a , a b a c a a, .....

 

3.

가장 많은 시약의 수가 절반 이하이고, 가장 많은 시약의 종류가 2개 이상일 경우 첫 번째와 동일하게 배치하면 조건을 만족할 수 있습니다.

예) 총 개수 9개 시약 a 3개, 시약 b 3개, 시약 c 3개

a b a c a c b c b

 

배치 방법

길이가 N인 result 배열을 선언 한 뒤, 개수가 많은 시약부터 개수만큼 차례대로 result 배열의 0, 2, 4, ... 짝수 인덱스를 끝까지 채워줍니다. 짝수 인덱스를 다 채워주면 홀수 인덱스를 채워주면 됩니다.

 

풀이

배치

위의 배치 방법을 토대로 배치를 해줍니다.

 

result[0]과 result[1]에 같은 시약이 들어있다면 가장 많은 시약의 개수가 전체 개수의 절반보다 많다는 것이므로, 조건을 만족하지 않는 경우입니다. 그러므로 -1 을 출력해줍니다.

 

result[0]과 result[1]에 다른 시약이 들어있다면 조건에 만족하도록 시약을 배치할 수 있다는 것이므로, result의 원소들을 공백으로 구분하여 순서대로 출력해줍니다.

 

 

해결

가장 개수가 많은 시약을 어떻게 배치할지 생각해내면 해결할 수 있는 문제였습니다.

 

문제 링크 : https://www.acmicpc.net/problem/20311

20311번: 화학 실험

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/20311.py