숫자 게임( BOJ 2923 )

문제

2923. 숫자 게임 : https://www.acmicpc.net/problem/2923

2923번: 숫자 게임

 

문제 파악하기

• a_i + b_i의 최댓값을 가장 작게 만들기 위해서는 한쪽에서는 최솟값만, 한쪽에서는 최댓값만 선택해서 더하면 됩니다.
• 예를 들어 a에 (1, 2, 3)이 있고, b에 (1, 4, 8)이 숫자는 (1, 8) / (2, 4) / (3, 1) 순으로 짝지어지며 이 때 9가 최댓값이 됩니다.
• 문제는 데이터가 최대 100,000개라는 점입니다. 어떻게 해야 제한 시간 안에 답을 구할 수 있을까요?

 

문제 해결하기

• 정답은 인덱스를 이용하는 방법입니다. 카운트 정렬이라고도 알려진 방법을 사용하면 문제를 해결할 수 있습니다.
• 핵심은 입력되는 두 숫자 a와 b가 100 이하의 자연수라는 점입니다. 1부터 100까지라면 인덱스로 표현할 수 있습니다.
• 숫자가 입력되면 해당 인덱스에 값을 1씩 증가시켜 해당 숫자의 개수를 표현해줍니다.
• 최댓값을 탐색할 때에는 각각의 배열을 1부터 100까지 살펴보면서 숫자가 있는 개수만큼 서로 연결시켜 조면 됩니다.
• 여기서 중요한 점은 한 배열은 작은 수부터, 나머지 배열은 큰 수부터 탐색을 시작해야 한다는 점입니다.

 

후기

100,000이라는 개수가 답답하게 느껴졌지만 역시 문제의 실마리는 문제 속에 있다는 걸 느낀 문제였습니다. 별다른 테크닉 없이 아이디어 만으로 풀 수 있는 문제여서 정말 재미있었습니다.