[BOJ] 17281번: ⚾ (Python)

📖  문제

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

17281번: ⚾

 

💻  코드

 

import sys
from itertools import permutations


def game(players, seq, N):
    score = 0
    i = 0
    for n in range(N):
        b1, b2, b3 = 0, 0, 0
        out = 0
        while out < 3:
            if players[n][seq[i]] == 0:
                out += 1
            elif players[n][seq[i]] == 1:
                score += b3
                b1, b2, b3 = 1, b1, b2
            elif players[n][seq[i]] == 2:
                score += b2 + b3
                b1, b2, b3 = 0, 1, b1
            elif players[n][seq[i]] == 3:
                score += b1 + b2 + b3
                b1, b2, b3 = 0, 0, 1
            elif players[n][seq[i]] == 4:
                score += b1 + b2 + b3 + 1
                b1, b2, b3 = 0, 0, 0
            i = i + 1 if i + 1 < 9 else 0

    return score


def solution():
    N = int(sys.stdin.readline().strip())
    players = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
    print(max(game(players, list(p)[:3] + [0] + list(p)[3:], N) for p in permutations([1, 2, 3, 4, 5, 6, 7, 8], 8)))


solution()

 

 

🙌  한마디

이렇게까지 시간복잡도 제한이 빡빡할 필요가 있을까..? 싶을 정도로 통과하기 어려웠다.

알고리즘의 효율성을 어떻게 하면 더 높일 수 있을까에 대해 고민해보게 만드는 문제였다.

시간 효율보다는 빠른 풀이에 초점을 두었던 나를 한번 돌아보았다.

 

고친 부분은 아래와 같다.

 

1. if if if if보다는 if elif elif elif로 쓰자. 즉 c언어의 switch문 처럼 동작하는 코드의 경우 if if if를 반복해서 쓸 경우 불필요하게 코드를 순회하게 된다.

2. 실행흐름이 도중에 끊기지 않도록 최대한 유의하자. spatial locality를 고려하여 예상하지 못한 자원의 사용을 최소화하자. ex)함수 호출, 실행흐름이 끊기도록 설계된 for, while문