[백준] 27172 - 수 나누기 게임

https://www.acmicpc.net/problem/27172

27172번: 수 나누기 게임

 

문제 한줄 이해

- 각자 숫자가 적힌 카드를 가지고 있을 때 내 카드로 상대방 카드를 나눴을 때 나머지가 0이면 +1점을 얻지만 반대로 나누어 지면 -1점을 얻고 다른 경우에는 무승부로 0점을 얻을 때 각 점수 구하기

생각난 풀이

문제를 읽고 생각난 필요한 조건들

1. 먼저 간단히 모든 경우의 수를 파악해주면 되는거 아니야? 라는 생각에 이중 포문을 사용했다.

import sys
n = int(sys.stdin.readline())
nlist = list(map(int,sys.stdin.readline().split()))
point = [0]*n

for i in range(n):
    for j in range(i+1,n):
        if nlist[j] % nlist[i] == 0 and nlist[i] % nlist[j] != 0:
            point[i] += 1
            point[j] -= 1
        elif nlist[j] % nlist[i] != 0 and nlist[i] % nlist[j] == 0:
            point[i] -= 1
            point[j] += 1
print(*point)

하지만 시간 초과 이때 n의 범위를 조건을 제대로 보지 않고 생각해서 이러한 문제가 발생했다.

 

2. 그래서 시간 복잡도를 줄이기 위한 방법 -> 결국 연산 횟수를 줄이는 것

그래서 에라토스의 체의 아이디어를 빌려봤다.

-> 입력 받은 숫자가 존재하는지 여부를 1000001의 길이 배열에 체크를 해주자 why? 파이썬의 리스트[i]는 O(1)으로 연산횟수 최소화

(조건에서 카드에 적힌 수가 같을 수가 없다고 한다. 그렇다면 N이 1000000이면 최대 숫자는 1000000이라는 뜻으로 숫자)

-> 입력 받은 숫자의 점수 배열만들기 why? 위의 이유와 동일

-> 이제 에라토스의 체의 아이디어를 사용

어떻게? 입력 받은 수를 한개씩 가져와 입력받은 값 중 제일 큰수까지만 배수를 해서

card[배수] == 1이면 result[현재수] +1, result[배수] -=1을 해주는 것이다.

import sys
n = int(sys.stdin.readline())
card = [0] * 1000001
result =[0] * 1000001
nlist = list(map(int,sys.stdin.readline().split()))

for i in nlist:
    card[i] = 1

maxnum = max(nlist)

for i in nlist:
    for j in range(i*2,maxnum+1,i):
        if card[j] == 1:
            result[i] += 1
            result[j] -=1

for i in nlist:
    print(result[i],end=" ")
print()