김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 14945 불장난 파이썬(Python)

문제 링크

조금 생각이 필요한 DP 문제.
dp[i]는 i번째 줄의 타일까지 이동했을 때의 경우의 수이다.
i번째 줄 타일까지 가려면 어차피 i-1번째 줄을 지나야 하므로 DP 문제가 된다.
다음 줄로 가는 방법은 각각 (아래, 아래), (아래, 대각), (대각, 아래), (대각, 대각)의 네 가지 경우가 있다.
그래서 나는 두 사람의 위치를 각각 저장해서 더해주는 방식으로 풀었는데, 풀고 나서 다른 풀이를 보니 사실 각각의 위치가 어딘지는 별로 중요하지 않고, 두 사람 간 거리만 생각하면 되더라.
개별적인 위치를 저장하려면 반복문을 하나 더 돌아야 하니 약간 비효율적인 방법으로 푼 셈이다.
어쨌든, 다음 줄로 가는 방법이 4가지인데, 인덱스가 범위를 벗어나는 경우도 있고, 또 (대각, 아래)같은 경우는 두 사람이 같은 타일에 들어가 충돌하는 경우가 발생할 수 있다.
예외처리를 해주면 좋겠지만 어차피 이전 배열의 인덱스 오버플로우가 일어난 위치의 값이 0이기 때문에 더해준다고 해도 문제가 되지는 않는다.

#!python

n = int(input())

# dp[i][j][k]는 i번째 줄 타일에서 앞사람이 j번째 타일, 뒷사람이 k번째 타일에 있는 경우의 수
dp = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]

# 1인 경우 그냥 같은 타일에서 그대로 나가면 되므로 예외처리
if n == 1:
    print(1)
else:
    # 초항은 1번 줄에 각각 0번, 1번 타일에 위치한 경우
    dp[1][0][1] = 1

    for i in range(2, n):
        for j in range(n):
            for k in range(j + 1, n):
                # case 1. 아래, 아래
                dp[i][j][k] = dp[i-1][j][k]
                # case 2. 아래, 대각
                dp[i][j][k] += dp[i-1][j][k-1]
                # case 3. 대각, 대각
                dp[i][j][k] += dp[i-1][j-1][k-1]
                # case 4. 대각, 아래
                dp[i][j][k] += dp[i-1][j-1][k]

    # 마지막 줄에 있는 모든 경우의 수를 더하고, 두 사람이 자리가 바뀌는 경우를 생각해야 하니 2로 나눈다
    print(sum(sum(l) for l in dp[-1]) * 2 % 10007)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑