[문제]
1부터 N까지의 정수가 쓰인 N 장의 카드로 진행되는 게임을 준비하고 있다. 이 N 장의 카드는 특별하게 고안된 셔플용 장치(Card Deck)로 들어가서 충분히 그리고 랜덤하게 섞이게 된다. 그런데 셔플 장치에서 섞인 카드 중에서 몇 장의 카드가 분실되었다는 사실을 알게 되었다. 즉 카드덱에 넣는 과정에서 실수로 몇 장의 카드가 빠진 것이다. 그리고 이 분실된 카드는 최대 2장이라는 사실도 알고 있다. 여러분은 이 셔플 장치에서 차례대로 나오는 카드를 모두 읽은 뒤 그 분실된 카드 번호를 찾아야 한다. 입력 파일에는 셔플 기계에 저장된 개의 카드 번호가 적혀있다. M은 $M = N - 1$ 혹은 $M = N - 2$이다.
[입출력]
입력파일 deck.inp의 첫 줄에는 정수 N이 주어진다. 단 $5 \leq N \leq 10000$이다. 이어지는 혹은 개의 각 줄에는 카드덱에서 나온 카드 번호가 한 줄에 하나씩 제시된다. 여러분은 이것을 읽은 다음 분실된 카드의 번호를 찾아서 한 줄에 하나씩, 최대 2개의 줄에 각각 순서대로 출력한다. 빠진 카드 번호가 2개일 경우에는 작은 번호부터 먼저 출력해야 한다.
단, 제한된 공간복잡도는 $O(1)$이다. 즉, 배열에 값을 저장할 경우 ac를 받지 못 한다.
[예제]
|
deck.inp |
deck.out |
deck.inp |
deck.out |
|
10 // N 8 4 1 10 5 9 2 7 //8번째 |
3 6
|
100 // N 98 41 ...(중략) ... 31 7 65 49 //99번째 |
56
|
[풀이]$O(\sqrt N)$
배열에 값을 못 집어 넣는다고? 그래.... 1장 빠질 때는 1부터 n까지 sum을 구해서 입력받는 값들을 빼주면 되니 간단하고... 2장일 땐 어째하지?
라는 고민을 샤워하는 30분동안 고민해봤는데 딱히 답이 나오질 않았다. 하지만, 직관적으로 알 수 있는건, 1장일 때 풀이를 그대로 적용하면 빠지는 두 수 $a, b$에 관해 $a + b$는 구할 수 있다.
그럼 이제 $a * b$를 알면 그냥 2차방정식 풀어버리면 되니 간단하다는 걸 알 수 있다.
그런데, 1장일 때 구했던 방식대로 $a * b$를 알 기 위해 n까지 모든 값을 곱하면 결국 $n!$을 구하는게 되니, 불가능하다.
그러니 $a^2 + b^2$을 구해서, $a*b$를 구하고, 이자방정식의 해를 풀어버리면 된다.
sqrt를 쓰는 멍청한 짓은 하지 않기위해 for loop으로 $\sqrt {b^2-4ac}$를 구해줬는데 더 좋은 방법이 있지 않을까 검색을 해보았지만 없는 듯 하다.
