[PS] [Baekjoon] 31577. 랜섬웨어와 비트코인

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

 

언어 : 파이썬 (Python3)

시작 : 2024.11.17 18:15

종료 : 2024.11.17 18:30

티어 : Gold IV

비고 : FunctionCup 2017 P4번

 

태그 :

해 구성하기?

 

문제 해석

 

20종류의 파일을,

15개의 컴퓨터에,

8개씩 나눠담는 문제다.

 

이 중 5개의 컴퓨터가 고장나더라도

다른 10개의 컴퓨터에서 20종류의 파일 모두를 수집할 수 있어야한다.

풀이

 

굳이 조건을 보지 않더라도,

총 $15*8 = 120$개의 파일을 나눠담아야하므로,

파일 한 종류 당 $120 / 20 = 6$개씩 고르게 나눠주면 된다.

 

1~6번 컴퓨터는 1번 파일, 7~12번 컴퓨터는 2번 파일, 13 14 15 1 2 3번 컴퓨터는 3번 파일 등등...

이렇게 하면 1~5번 컴퓨터가 고장나도 6번 컴퓨터에 1번 파일이 살아있게 된다.

 

문제 해석할 때 숫자 이슈만 조심하자. (...)

코드 잘못 짜서 8개까지만 담을 수 있던 걸 15종류씩 담아버린다던지

문제 잘못 읽어서 20종류 파일을 15종류로 오해한다던지

뇌절 와서 컴퓨터는 15대 뿐인데 20대 있다고 잘못 읽는다던지...

 

코드

 

풀이 1) 성공, 0ms

import sys
from itertools import combinations
input = sys.stdin.readline

def validate(arr):
    comb = combinations([i for i in range(15)], 5)
    for c in comb:
        print(c)
        s = set()
        for i in range(15):
            if i in c:
                continue

            for a in arr[i]:
                s.add(a)

        if len(s) < 20:
            return False

    return True

arr = [list() for _ in range(15)]
wheel = 0
for i in range(20):
    for j in range(6):
        arr[wheel].append(i+1)
        wheel += 1
        wheel %= 15

for a in arr:
    print(*a)

if validate(arr):
    print('check')
else:
    print('False')

 

해당 코드의 출력값을 답으로 제시했다.

사실 "알고리즘"이라고 부르기엔 좀 애매한 감이 없지 않아 있는 문제.