[백준 / BOJ] 20921 그렇고 그런 사이

문제

출처 : https://www.acmicpc.net/problem/20921

20921번: 그렇고 그런 사이

환주는 두명을 그렇고 그런 사이로 만드는데 전문가이다.

그렇고 그런 사이가 될려면, 다음 조건을 만족해야한다.

(P(i)가 갖고있는 숫자가 P(i+a)보다 커야함) (단, a>0)

 

환주의 친구의수 N, 그렇고 그런 사이로 만들어야하는 쌍의수 K가 주어졌을때, 그렇고 그런 사이를 만드는 경우를 출력하는 문제다.

---

풀이

재밌는..? 문제였다.

문제를 처음 봤을때는 감이 잘 안잡혔는데,(dp라고 예상했었음) 문제의 예제를 직접 해보니 그리디라는것을 알았다.

 

아이디어는 다음과 같다.

 

남아있는 숫자로 그렇고 그런 사이를 늘리는것은 어려우나, 줄이는것은 쉽다.
(오름차순으로 지정해주면 되기때문임.)
즉, 항상 가능한 최대의 관계를 맺어줘도 손해볼것이없고, 그리디로 풀수있음

 

N명의 친구들을 각각 1번친구 2번친구 3번친구 ... N-1번친구 N번친구라고 하자.

1번친구부터 탐색하며, 현재 맺을수있는 관계중 K를 초과하지 않는관계중 가장큰것을 선택해주면된다.

 

주요 소스코드

   private void getRelation(){
        for(int i = 0; i < N; i++){
            int relNum = findRelation(K);
            K -= remainNumber[relNum];
            setRemainNumber(relNum);
            System.out.print(relNum + " ");
        }
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/tree/master/BOJ%20source%20code/20921

devxb/JJUNalgo