4880. [파이썬 S/W 문제해결 기본] 5일차 - 토너먼트 카드게임

알고리즘/sw

4880. [파이썬 S/W 문제해결 기본] 5일차 - 토너먼트 카드게임_python

HAN_PY 2020. 3. 29. 00:01

4880. sw expert academy 토너먼트 카드게임

문제의 저작권은 SW Expert Academy에 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def sol(st, en):
    selection = [st, en]
    solve = [[0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0]]
    res = solve[data[st]][data[en]]
    return selection[res]
 
def div(start, end):
    if start == end:
        return start
    st = div(start, (start+end)//2)
    en = div((start+end)//2 + 1, end)
    return sol(st, en)
 
 
TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    data = [0] + list(map(int, input().split()))
    result = div(1, N)
    print("#%d %d"%(tc, result))

cs

Divide and Conquer (분할정복)

위의 문제 풀이 방법은 분할 정복 방법으로 접근해서 풀었다. 재귀에 대한 기본이 없다면 이해하기 힘들다.

분할 정복에 대한 개념은 알고리즘 부분을 참고 하면 좋을 듯하다.

가위바위보를 좀 신기 하게 접근했다.

def sol(st, en):

selection = [st, en]

solve = [[0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0]]

res = solve[data[st]][data[en]]

return selection[res]

1 가위

2 바위

3 보

solve[x][y]라고 예를 들면 x와 y이에 가위바위보 중 하나가 들어가고

x가 이기거나 비기면 0을 출력하고 y가 이기면 1을 출력하게 했다.

그 결과 값으로 미리 list로 만들어논 selection에 넣으면 승자가 나오게 된다.