카드

 

[문제] 1부터 N까지의 서로 다른 정수가 쓰여진 N 장의 카드가 있다. 이 카드를 섞어 그 섞인 순서를 어떤 파일에 기록하였다. 그런데 이 과정 중에 우리는 실수로 2장의 카드를 분실하였다. 이 때문에 우리가 가진 파일에 기록된 숫자는 모두 N-2개 이다. 여러분은 이 N-2개의 숫자를 읽어서 빠진 2장의 카드에 적힌 수 a, b (단 a<b)를 찾아야 한다. 단 카드 장수 N은 문제마다 다르게 주어진다.

 

 이 문제는 크기 N인 배열 int numbers[N]를 이용하면 쉽게 해결할 수 있다. 그러나 이 경우에는 크기 N인 정수 배열을 준비해야 하는 부담이 잇다. 그러나 이번 과제에서 여러분은 읽은 카드번호를 기록하는 배열(array, list)을 사용하지 않고 빠진 2 숫자를 찾아야 한다. 단위 정수 변수 (int)만 사용이 가능하다.

 

[입력] 입력파일 cards.inp의 첫 줄에는 정수N이 주어진다. 단 5<=N<=500 이다. 이어지는 N-2개의 각 줄에는 1부터 N가지의 수 중에서 하나의 숫자가 중복없이 한 줄에 하나씩 제시된다. 여러분은 이 빠진 2개의 숫자를 찾아서 출력파일 cards.out의 2개의 줄에 각각 순서대로 출력한다. 단 여러분은 읽은 숫자를 기록하기 위한 배열 또는 그와 유사한 기억장소를 사용해서는 안된다. a, b의 출력 순서는 오름차순이다.

 

[예제]

cards.inp                 cards.out

10                         3

8                          6

4

1

10

5

9

2

7

 

cards.inp                cards.out

300 // N                98

123                      234

87

231

57

...

6

118

293

 

 

[실패한 풀이1]

 배열을 사용할 수 있으면 굉장히 쉽게 풀 수 있는 문제지만, int형 변수만 사용 가능하다고 하여 생각을 많이 해야했다.

다행히 주어지는 숫자가 1부터 N까지 1씩 증가하는 숫자들이다. 이를 이용하여, 1부터 N까지 모든 수들의 합과 주어진 1부터 N-2까지 2개의 수가 빠진 것들의 합을 빼면 우리가 알고싶은 값의 합인 a+b가 나오게 된다. 또, 1부터 N까지 모든 수들의 곱과 주어진 1부터 N-2까지 2개의 수가 빠진 것들의 곱을 나누면 우리가 알고 싶은 값의 곱인 a*b가 나오게 된다. 우리가 알고 싶은 두 수의 합과 곱을 이용하여 두 수를 찾을 수 있었다.

 -> 이 방법으로 풀게 되면 N이 너무 클때 N!을 구하면 그 수가 매우 커지기 때문에 int형 변수에 값을 저장하는것이 불가능하다.

코드: https://github.com/sak5010/PNU_Algorithm_2020/blob/master/card_first_attempt.cpp

sak5010/PNU_Algorithm_2020

[성공한 풀이]

 교수님의 풀이 강의를 듣고 다시 풀어 해결하였다. 일단 내가 한 방법으로 빠진 두 수의 합인 a + b를 찾고, 제곱의 합 공식 n(n+1)(n+2)/6 을 이용하여 a^2 + b^2을 찾는다. a + b와 a^2 + b^2을 연립방정식을 풀어 a와 b를 찾으면 되는 문제였다.

코드: https://github.com/sak5010/PNU_Algorithm_2020/blob/master/cards.cpp

sak5010/PNU_Algorithm_2020