27172번 수 나누기 게임

문제 설명

이번 문제는 아래의 규칙으로 카드 게임을 실시하고 각 플레이어가 얻은 점수를 출력하는 문제입니다.

• 각 사람이 카드를 한 개씩 받게 됩니다. (카드는 1~1,000,000 사이의 수)
• 카드 게임은 두 명이서 진행됩니다.
• 각 사람이 자신의 카드를 냈을 때 자신의 수로 다른 사람의 수를 나눴을 때 나머지가 0이면 승, 자신의 수가 다른 사람의 수에 적힌 수로 나누어 떨어지면 패, 둘 다 아니라면 무승부
• 승리한 플레이어는 1점을 얻고 패배한 플레이어는 1점을 잃습니다. 무승부인 경우 점수의 변화가 없습니다.
• 본인을 제외한 모든 플레이와 정확히 한 번씩만 게임을 실시합니다.

 

문제 풀이

아이디어

시간 복잡도

플레이어의 수가 100,000이므로, 모든 플레이어들의 모든 플레이를 for문으로 반복하면서 결과값을 구한다면 10^10 정도의 시간 복잡도가 나오므로 시간초과가 나올 것입니다.

 

배수 사용

주어진 숫자 카드를 작은 수부터 자신의 배수 중에 주어진 카드가 있는지 확인하고 해당 카드가 있다면 -1을 하고 자신을 +1을 해주는 식으로 나아가면, 더 적은 시간 안에 카드를 잡은 플레이어의 점수를 찾을 수 있을 것입니다.

 

 

풀이

변수 선언

주어진 수의 점수를 저장할 result 변수를 선언해줍니다. (result = [-1, -1, ...] 인 길이가 1,000,001입니다.)

주어진 숫자 카드를 배열 array에 저장합니다.

 

순회

우선 주어진 카드의 수를 인덱스로 하는 array배열의 원소를 0으로 바꿔줍니다. (해당 숫자는 주어진 카드 중에 하나라는 것을 알기 위해)

주어진 숫자 카드 배열을 오름차순으로 정렬을 한 뒤, 작은 수부터 순회를 시작합니다.

현재 순회중인 숫자 카드 array[i]의 배수를 순회합니다. 배수(여기서 array[i]*j라고 가정) 중에 주어진 카드가 존재(result[array[i]*j] >= 0인 경우)한다면, 해당 result[array[i]*j]를 1 더해주고 result[array[i]]를 1 빼줍니다.

 

이런 식으로 순회를 진행하면, 해당 숫자가 패배하는 경우 상대가 +1이 되고 자신은 -1이 됩니다. 

 

출력

문제에서는 자신이 승리할 경우 +1이 되는 것이 규칙이므로 result배열에서 구한 값에 -1을 곱한 값이 답이 됩니다.

 

 

 

해결

이번 문제는 이게 더 시간 복잡도가 낮을 것이라는 확신 없이 푼 문제라 확실하게 풀었다라고 말하기는 어렵지만, 다시 복기를 해보면서 확신을 가질 수 있었던 문제였습니다.

 

문제 링크 : https://www.acmicpc.net/problem/27172

27172번: 수 나누기 게임

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/27172.py