park780172   4년 전

우선 저는 이 문제를 보고, 모든 경우를 탐색할 수 밖에 없고,

그래야 어떤 숫자가 나오는지 알 수 있기 때문이라고 생각했습니다.

즉, 모든 경우의 합을 먼저 구하고(첨부한 코드의 bt()),

그것을 활용해 이중 for문을 활용해 정답을 구합니다.

그런데 생각해보니, 숫자가 많을수록 st에 들어가는 수(합)가 많아지는 것 같더라구요.

그래서 이중 for문에서 시간 초과가 걸립니다.

어떤 알고리즘을 설계해야 시간 초과를 안 나게 할 수 있을까요?

답변해주시면 감사하겠습니다.

chogahui05   4년 전

실버급은 아닌 거 같은데.. 크흠.. 아이디어 하나만 드릴게요.

1 2 3 4 5 6 7이 있을 때 처음에 1을 제거하면

(2 7) (3 6) (4 5)가 같아야 합니다.

2를 제거한 경우

(1 7) (3 6) (4 5)가 같아야 하고요.

3을 제거한 경우

(1 7) (2 6) (4 5)가 같아야 합니다.

이런 식으로 종이에 잘 경우의 수를 따져 보면, 바뀌는 조건 이벤트는 단 하나밖에 없음을 알 수 있어요. 그것을 이용하시면 됩니다.

park780172   4년 전


@chogahui05 

실버급이라는 것은 무슨 말씀이신가요?

chogahui05   4년 전

solved.ac 난도가 실버급은 아닌 거 같다는 의미입니다..

park780172   4년 전

@chogahui05

아 그렇군요

여튼 애초에 풀 당시에는 제가 완전 잘못 생각하고 접근하고 있었어요 ㅋㅋ

왜 저런 큰 실수를 했는지.. 당시 저의 두뇌회전이 잘 안 됐나보네요..

댓글 감사합니다.

저는 dfs로 모든 경우의 수를 다 탐색해서 풀었는데,

말씀해주신 방법도 고려해보겠습니다.

댓글을 작성하려면 로그인해야 합니다.