[백준/파이썬] 14222번 배열과 연산

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

14222번: 배열과 연산

문제 해석

 

n크기의 배열에 k만큼 수를 더하는 연산이 가능하다.

위의 연산을 통해 1~n까지 모든 수가 1개씩 존재하는 배열을 만들 수 있는지 출력하라.

---

코드

 

n, k = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse = True)

check = [0] * (n + 1)

for i in range(n):
    s = 0
    temp = arr[i]
    while arr[i] + s * k <= n:
        temp = arr[i] + s * k
        if 0 < temp < n + 1 and check[temp] == 0: break
        s += 1
    if 0 < temp < n + 1 and check[temp] == 0: check[temp] = 1
    else:
        print(0)
        exit(0)
print(1)

---

문제 풀이

 

배열을 내림차순으로 정렬한 뒤 하나씩 확인한다.

가장 큰 수부터 확인하며 check 배열에 채워 나가면 나중에 나오는 수는 항상 check 배열이 비어있게 된다.

따라서 최대한 큰 수를 먼저 check 배열에 채우고, 차례대로 check배열에 채워가고 채워져 있다면 k만큼 지속적으로 더해

배열을 채워나가면 된다. 즉 그리디 알고리즘으로 생각하며 풀면 된다!

 

모두 채웠다면 1 중간에 채울 수 있는 수가 하나라도 존재하면 0을 출력하면된다.

-> 머리속에 있는 생각을 글로 못적겠다...

반복문전에 변수를 선언해서 사용하자.. 반복문이 안들어가 선언이 안되면 Nameerror가 발생한다....