초등 수학( BOJ 11670 )

문제

11670. 초등수학 : https://www.acmicpc.net/problem/11670

11670번: 초등 수학

 

문제 파악하기

• 모든 입력값은 항상 3가지 결괏값을 가질 수 있습니다.
• 입력된 모든 값이 서로 다른 결괏값을 가질 수 있는지와 다르다면 어떻게 다른지 출력하는 문제입니다.
• 입력되는 값이 10^-6 ~ 10⁶ 사이의 정수이기 때문에 int형보다는 long long int형이 계산하기 편해 보입니다.
• 입력 값이 하나의 결과에 대응되어야 하기 때문에 이분 매칭 알고리즘을 이용하면 됩니다.

 

문제 해결하기

• 문제를 그래프 바꾸기는 쉽습니다. 입력값과 결괏값으로 나눠서 나올 수 있는 결괏값에 입력값을 연결하면 됩니다.
• 다만, 결괏값은 중복될 수 있기 때문에 중복된 값들을 제거해야 합니다.
  Ex. result.erase( unique(result.begin(), result.end()), result.end() );
• 입력값과 결괏값을 그래프로 변환했으면, 이분 매칭을 진행하면 됩니다.
• 마지막으로 결괏값을 출력하려면 이분 매칭에 사용한 배열을 사용하면 쉽게 마무리됩니다.

 

후기

이분 매칭을 익히는데 유용한 문제로 보입니다. 이분 매칭을 연습하고 싶다면 추천하고 싶은 문제라고 할 수 있겠네요. 다만, 중복된 값을 제거하고 찾는데 다양한 방법이 사용될 수 있다고 생각합니다.