[일간임무] - 단체사진찍기

Permutation으로 금방 풀긴 했는데 또 시간 초과에서 걸려버렸습니다. 어차피 8명을 모두 세워야 하기 때문에 8명을 서로 다른 방법으로 세우고 나서 조건을 검사했습니다. 8!이라는 워낙 많은 케이스를 검증해야 하기 때문에 시간을 많이 잡아 먹는 것은 감안했지만 추측하기를 Satisfy함수에서 귀여운 Friends의 Index을 찾는 과정이 문제일 거라 생각했습니다.

그런데 그게 아니고 offset을 integer로 변환하는 과정이 문제였습니다. 그냥 char을 int로 cast해서 풀면 시간 초과를 해결할 수는 있었습니다. 아래의 코드 몇 줄이 시간 초과의 원인이라는 게 참 웃깁니다.

figure 1a

figure 1a의 코드를 다음과 같이 바꾸니 성공은 합니다.

figure 1b

figure 1c

무려 6초나 걸려서 다른 사람들도 그런가 확인을 좀 했습니다. Next_Permutation을 다시 공부하면 좋을 것 같습니다.

Elapsed Time : 30min

1. Permutation

2. ** Next Permutation