[TIL] 동적 프로그래밍 문제 풀이3

1. 문제 풀이 연습

1. 11660번 - 구간 합 구하기 5

import sys

N, M = map(int, sys.stdin.readline().split())
table = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 누적합을 저장할 이차원 배열
dp = [[0] * (N+1) for _ in range(N+1)]
for i in range(1, N+1) :
    for j in range(1, N+1) :
        dp[i][j] = table[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]

# 원하는 구간합 구하기
for _ in range(M) :
    x1,y1,x2,y2 = map(int, sys.stdin.readline().split())
    sum = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
    print(sum)

누적합 구하기

전체 누적합을 먼저 구한 다음에 구간합을 구한다.
이때 겹치는 부분이 생기기 때문에 이를 주의해야한다.

---

2. 10986번 - 나머지 합

import sys

N, M = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

# 누적합을 저장하기 위한 변수
preSum = nums[0]
# 각 누적합을 M으로 나눈 각 나머지의 개수를 저장할 배열
div = [0] * M

# 0번째 값 먼저 저장 - 초기화
div[preSum % M] += 1

for i in range(1, N) :
    preSum = preSum + nums[i]
    div[preSum % M] += 1

count = 0
# 각각 1번부터 구한 누적합에서 가능한 개수 
# 무조건 2개를 선택하여 조합한다.
for i in range(M) :
    if div[i] > 1 :
        count += (div[i] * (div[i]-1)) // 2

# 0번 부터 구한 누적합에서 가능한 개수도 더해준다.
print(count + div[0])

코드 원리

---

2. DP 문제풀이

1. 2098번 - 외판원 순회

import sys

N = int(sys.stdin.readline())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
INF = float('inf')
# 0으로 초기화 / INF로 초기화하면 시간초과 발생
dp = [[0] * (1 << N) for _ in range(N)]

# current : 현재 도시 / visited : 방문 여부 저장 정수
def dfs(current, visited) :
    # 모든 도시를 돌았다면 -> visited = 2^N-1일 경우
    if visited == (1 << N)-1 :
        # 마지막 도시인 현재 도시에서 시작도시로 가는 길이 존재하면
        if city[current][0] :
            # 현재 도시에서 시작 도시로 가는 비용 반환
            return city[current][0]
        else :
            return INF
    
    # 만약 현재 도시에서 다음에 갈 도시에 대한 비용을 이미 계산했을 경우
    if dp[current][visited] :
        return dp[current][visited]
    
    dp[current][visited] = INF
    for i in range(1, N) :
        # 길이 존재하고 현재 방문하지 않았으면 -> 방문 여부 확인 & and 연산자 사용
        if city[current][i] != 0 and visited & (1 << i) == 0 :
            # 방문 체크 -> | or 연산자 사용
            dp[current][visited] = min(dp[current][visited], dfs(i, visited | (1 << i)) + city[current][i])
    return dp[current][visited]

print(dfs(0, 1))

비트 연산자 사용법

비트 연산자, DP dfs를 사용하는 문제로 예전에 완전탐색 공부할 때 기본적인 틀은 알고 있었다.
문제는 비트 연산자를 사용하는 방법이었는데 간단하게 위의 그림과 같이 사용법을 익혔다.

1. 모두 방문 완료했을 경우
    : (1 << N) -1 = 2^N -1
2. 방문 여부를 확인하는 경우
    : visited & (1 << i ) → i번째 자리만 1로 설정하고 나머지는 0으로 설정한 뒤 and 연산 실행
      만약 방문하지 않았으면 위의 결과가 0 / 방문했었으면 결과가 2^i가 나타날 것이다.
3. 방문 여부 체크하는 경우
    : visited | (1 << i) → i번째 자리리만 1로 설정한뒤 or 연산 실행
      원하는 자리만 1로 변경될 수 있도록 한다.

이때 주의할 점은 dp 배열을 어떻게 초기화하는냐 이다.
처음에 INF로 초기화하니까 시간초과가 계속 발생했다.
< 오류 참고 > https://www.acmicpc.net/board/view/106935
다른 질문글을 확인해보니 나와 같은 문제를 가진 사람을 발견해서 읽어보았다.
참고하여 dp배열을 0으로 초기화하여 제출하니 성공했다.

< 문제 참고 블로그 >
https://hongcoding.tistory.com/83