[백준 / BOJ] 1248 맞춰봐

문제

출처 : www.acmicpc.net/problem/1248

1248번: 맞춰봐

규현이는 -10 ~ 10 까지 총 21개의 숫자를 알고있으며, 이 수를 구간합으로 나타냈다.

S[i][j] 는 i번째 숫자부터 j번째 숫자까지의 구간합이며 이 값이 양수면 +, 음수면 -, 0이면 0이 된다. S[i][j]의 각 원소들이 모두 주어졌을때 원래 수열이 무엇인지 찾는 문제였다.

 

풀이

완전탐색(백 트래킹)으로 풀리는 문제였다.

 

각 칸에 숫자를 넣어보고 숫자를 넣을수있다면, 재귀를 호출하고, 아니라면 다음 숫자를 넣어보는 식으로 구현했다.

총 10개의 숫자가 들어갈수 있으므로 최대 탐색시간은 10!이 되며,

 

숫자를 넣을수있는지 체크하는 과정마다 최대 10번 반복하므로 총 시간복잡도는 N*N!이 된다.

 

숫자의 범위가 -10 ~ 10이라 생각하고 완전탐색을 수행할경우 잘못하면 20!이 되어서 시간초과가 나오는데, 

시간초과를 피하기위해서 S[i][i] ex) S[1][1], S[2][2] ...등이 표현하는것이 무엇인지 파악하는게 중요했다.  

위 정보는 각각 자기 자신이 양수인지 음수인지 나타내는데, 자신의 부호가 무엇인지 알고있다면, 음수은 양수를 제외하고 최대 10번 반복으로 자신이 무슨숫자인지 알수있다.

예를들어 문제의 예제 입력 1의 경우, 배열 S는 

- + 0 +

x + + +

x x - -

x x x +

와 같이 초기화 될것이다. 이때, i = i인 지점을 보면,

첫번째 숫자는 음수, 두번째 숫자는 양수, 세번째 숫자는 음수, 네번째 숫자는 양수라는 사실을 알수있다. 

따라서 자신의 부호와 반대되는 부호의 경우 탐색하지 않고, 최대 10번 탐색으로 구현하면 시간초과를 피할수있다.

 

이 외에 무슨 숫자가 들어가야하는지 판단하는부분은

 

1. i위치에 임의의 숫자 하나를 넣는다 (1~10)

2. 이때, 지금까지 넣은 숫자들과 비교하며 구한 구간합이 입력과 같은지 확인한다.

 

위 과정을 백트래킹으로 구현하며 모든 숫자를 넣어보면 된다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1248%20%EB%A7%9E%EC%B6%B0%EB%B4%90/main.cpp

devxb/JJUNalgo