Red Salmon

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

내답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/9813.cpp

하.. 이문제 그냥 간단한 재귀일줄 알았다.. 하지만 매우 손이 많이가는 문제였다. 괜히 정답자가 1명인게 아니었다. 

먼저 나는 정답을 맞지 못했다. 그러나 내 답이 맞다고 생각한다. 정답자 소스에서 반례를 찾았기 때문이다.

먼저 문제설명을 하자면 숫자가 5개 입력이 들어오고 첫번재 수가 -1이면 프로그램이 종료이고 그게 아니라면 계속 입력을 받는다.

수는 1번째부터 4번째까지의 수로 어떻게 계산을 하든 5번째 수를 만들도록 하는것이며 최종적으로 불가능하다면 NO! 를 출력하는 것이다. 

이 문제는 내가 정말 많이 해맸다. 문제 해설이 약간 빈약했던것 같다.

우선 기본적인 접근은 다음과 같다.

1. +, -, *, / 이 네가지 산술기호를 재귀로 전부 할당한다 수는 4개뿐이므로 산술기호는 3개로 한정되어 있다. +++부터 ///까지 모두 대입한다. 

2. 괄호를 칠 수 있다. 하지만 문제에서 하나의 연산자만 가능하다고 하였으니 이중괄호는 없다고 가정하고 시작한다. 괄호는 패턴을 나눠보면 다음과 같다.

//case 1 (a, b), c, d

//case 2 a, (b, c), d

//case 3 a, b, (c, d)

//case 4 (a, b), (c, d)

//case 5 (a, b, c), d

//case 6 a, (b, c, d)

//case 7 a, b, c, d

위와 같이 총 7가지 경우가 나온다.  이 경우에 맞춰 전부 대입해보면 된다. 

하지만 유의할점이 있다.

문제 어디에서도 수가 바뀌지 않아도 된다는 말은 없다. 즉 1번째 수부터 4번째 수까지 위치가 바뀌기도 한다. 

예를들어 a, b, c, d 로는 어떠한 방법으로도 e를 만들 수 없더라도 d a c b 이렇게 순서를 바꾸면 될 수도 있다. 실제로 이런 경우는 존재한다.

그러므로 다시 4가지 수를 모든 경우의 수에 따라 재귀를 돌려줘야한다. 

그리고 두번째 유의할 점

나누기는 언제나 짜증나는 것인데, 만약 예외처리를 하지 않는다면 1/0 이렇게 0으로 나누라는 경우가 발생할것이고 프로그램은 죽게 될 것이다. 그렇기 때문에 반드시 예외 처리를 해야한다.

그리고 3/2 이런수는 당연히 1.5이다. 하지만 int로만 처리하면 이 수는 1이 되고 e가 1이라면 같다고 판단할 수 있다. 그러므로 이 부분도 처리를 따로 해줘야 피해갈 수 있다.

그럼에도 불구하고 나는 오답을 맞았다. 그리고 구글링을 통해 정답자의 소스를 구했는데 특이한 반례를 찾았다.
원문 링크

16 15 17 50 9 다음의 수가 들어오면 나는 ok를 주고 정답자는 no를 준다. 

그런데 이경우 수를 50 17 15 16 9 이렇게 정렬하고 식을 50 / (17-15) -16 이렇게 가공하면 9가 나올 수 있다. 그런데 정답자 소스에는 이 경우 NO를 출력하게 하였다. 아마 이 부분의 차이와 같은 문제로 오답을 맞은 것 같다. 

그런데 신기한건 30 4 2 5 10 이수를 주고 동일한 패턴을 대입하면 정답자소스도 OK를 주게 된다. 뭔가 이건 이상하다.

그래서 나는 내 소스가 맞고 정답테스트케이스 및 정답소스가 틀렸다고 생각했다. 뭐 케이스를 다 열어보고 대조를 해봐야 알겠지만, 확실히 이상한 부분이고 내가 맞다고 생각한다. 

그래서 셀프 정답처리를 하고 넘어가야겠다. 

P.S.

소스를 최대한 간소하게 하려고 함수를 이것저것 써넣으며 반복시켰는데, 그래도 길다...