[백준] 5557 1학년

참고: https://www.acmicpc.net/problem/5557

5557번: 1학년

---

주어진 수들의 연산(+, -) 결과가 배열의 마지막 수가 되는 경우의 수를 구하는 문제입니다.

 

일단 문제에서 주어진 단서들을 나열합니다.

 

수의 범위는 0이상 20이하이고, 배열의 크기는 3이상 100 이하 입니다. 그리고 올바른 등식의 개수의 범위가 2^63 - 1까지 입니다.

 

여기서 얻을 수 있는 힌트는 배열의 크기가 그리 크지 않으므로 이중 for문 정도는 사용할 수 있고, 정답을 저장할 변수 타입은 자바라면 long이 적당할 것 같습니다.

 

그리고 주어진 배열 arr이 [8 3 2 4 8 7 2 4 0 8 8] 라고 가정합니다. 

arr[0] + arr[1] = 11, arr[0] - arr[1] = 5 

11 + arr[2] = 13, 11 - arr[2] == 9 ....

 

연산을 할 때 마다 그 개수가 2^N 만큼 커집니다. 매우 많은 수가 나올 수 있다는 것이고, 그렇다는 것은 동일한 결과가 나올 경우도 존재한다는 것입니다.

 

다시 말하자면, 7 - 2, 8 - 3, 9 - 4, 11 - 6 의 연산 결과가 모두 5로 동일하기 때문에 굳이 하나씩 저장할 필요 없이, 나타난 결과의 카운트만 저장하고, 다음에 5 와 어떤 수의 연산 결과 A가 나올 경우 A가 나오는 카운트를 5가 나온 카운트 만큼만 더해주자는 것 입니다. 결론적으로 이 문제는 중복된 하위 문제들로 이루어져 다이나믹 프로그래밍으로 풀 수 있습니다.

 

이제는 고민할 것 없이 다이나믹 프로그래밍으로 코드를 작성하되, 연산의 결과가 0이상 20 이하인 것만 신경써주면 됩니다.

 

시간 복잡도는 굳이 말하자면 O(20 * N) 이니 O(N) 시간에 해결할 수 있습니다.

 

Python

Java