BOJ_14864_줄서기

시작

줄서기 문제는 Ad-hoc 으로 문제 분류가 되어있습니다.

이 알고리즘을 찾아보니, 창의력 문제 정도로 찾아볼 수 있었습니다. 

 

규칙?

문제를 읽고 손으로 끄적이다가 대강 넣어보니 이렇게 들어가는 구나 이해를 했습니다. 

아래는 그 손으로 끄적인것을 그림으로 도식화 한것입니다. 

 

 

 

 

 

 

 

 

 

근데 막상 규칙을 찾아보려 하니 규칙이 눈에 띄진 않았지만 

괄호안에서 왼쪽, 오른쪽 사이에는 대소 비교관계가 있고

왼쪽이 오른쪽보다 크기 때문에 묶어 생각해보면

학생1이 가진 숫자는 최소 2개의 숫자보다 크게 됩니다. 

그렇기 때문에 +2 라는 표시를 했고

 

학생5의 경우에는 최소 3개의 숫자보다 작게 됩니다.

마찬가지로 -3라는 표시를 했습니다. 

 

그렇게 보니, 초기 값 N=5라면 Array 각 인덱스에 1,2,3,4,5 가 순서대로 들어가 있고 

왼쪽의 경우에 해당하면 +, 오른쪽에 해당하면 - 를 해주면 됩니다. 

그리고 init 값이 1,2,3,4,5 가 아니어도 다른 값을 대입하게 되면

해당 경우에는 1~N 범위 사이에서 값을 구할 수 없기 때문에 문제에서 요구하는 답을 찾을 수 없게 됩니다. 

 

Code