대학에서 알고리즘 대회 우승 방법 — 스마트 트릭으로 | Mahdi Shamlou

Source: Dev.to

소개

오늘은 평소 LeetCode 게시물과는 다른 내용을 공유하고 싶습니다.
최근 이슬람 아자드 대학교에서 알고리즘 및 프로그래밍 대회에 참가해 우승했습니다! 🎉

문제 설명

두 개의 큐브에 숫자를 적어, 큐브를 나란히 놓아 0부터 n까지 모든 숫자를 표시할 수 있도록 설계해야 했습니다.

규칙

• 각 큐브는 6개의 면(6개의 숫자)을 가집니다.
• 큐브를 나란히 놓아 0 → n까지 모든 숫자를 만들어야 합니다.
• 가능한 경우 큐브 구성을 출력하고, 그렇지 않으면 "Impossible"를 반환합니다.

중요한 세부사항: 6을 회전시켜 9로 사용할 수 없습니다.

관찰

처음 보면 이 문제는 완전 탐색처럼 보입니다:

1. 각 큐브에 대한 숫자 조합을 생성합니다.
2. 모든 순열을 테스트합니다.
3. 0부터 n까지 모든 숫자를 표시할 수 있는지 확인합니다.

하지만 유효한 구성의 수는 매우 제한적입니다. 필요한 숫자를 논리적으로 분석하면 최대 가능한 상한을 결정할 수 있습니다.

9라는 숫자를 명시적으로 필요로 하고 6을 9로 재사용할 수 없기 때문에 표시할 수 있는 가장 큰 n은 30입니다. n이 30을 초과하면 답은 "Impossible"입니다.

해결책

유효한 구성은 수작업으로 미리 계산할 수 있습니다:

• 큐브 1: [1, 2, 3, 4, 5, 6]
• 큐브 2: [0, 1, 2, 7, 8, 9]

이 배열을 사용하면 0부터 30까지 모든 숫자를 표시할 수 있습니다.

코드 (Python)

def two_cubes_solution(n):
    """Return the digit configuration for two cubes that can display
    all numbers from 0 to n, or 'Impossible' if n > 30."""
    # Impossible case
    if n > 30:
        return "Impossible"

    # Pre‑calculated cube faces (solved manually)
    cube1 = [1, 2, 3, 4, 5, 6]
    cube2 = [0, 1, 2, 7, 8, 9]

    return cube1, cube2


# Example usage
if __name__ == "__main__":
    n = int(input())
    print(two_cubes_solution(n))

복잡도: 시간 O(1), 공간 O(1).

교훈

때때로 가장 현명한 알고리즘은 논리를 한 번 (예: 손으로) 해결하고 코드는 간단하게 유지하는 것입니다. 다음 대회 문제도 곧 공유하겠습니다—그 문제는 훨씬 더 알고리즘 중심이었습니다.