배극곰의 IT식량창고

문제링크

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

문제설명

1

10

문제풀이

이차원 DP리스

코드

N = int(input())
D = [[0 for i in range(10)] for _ in range(N)]
answer = 0

for i in range(10):
    D[0][i] = 1

for i in range(1, N):
    for j in range(10):
        for k in range(j, 10):
            D[i][k] = (D[i][k] + D[i-1][j]) % 10007

for i in range(10):
    answer = (answer + D[N-1][i]) % 10007

print(answer)

문제링크

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

문제설명

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

3

문제풀이

LIS를 응용하면 쉽게 풀수 있는 문제였다.

코드

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
D = [1] * N

# 오름차순 정렬
arr = sorted(arr, key = lambda x: x[0])

# LIS 어떻게 활용할지 생각
for i in range(1, N):
    for j in range(i):
        if arr[i][1] > arr[j][1]:
            D[i] = max(D[i], D[j] + 1)

print(N - max(D))

문제링크

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

문제설명

6
10 20 10 30 20 50

4

문제풀이

처음 시도한 생각

dp리스트 원소를 튜플로 넣어 (i번째까지 제일 큰 원소, 수열길이) 정보를 저장하려고 했다.

틀린풀이

N = int(input())
arr = list(map(int, input().split()))
D = [(0, 0) for _ in range(1001)]
cnt = 1

# dp리스트에 튜플 형태의 원소로 저장하는데
# D[i] = (i번째까지 제일 큰 원소, 수열길이) 형태로 저장.
D[0] = (arr[0], cnt)

for i in range(1, N):
    if arr[i] > D[i-1][0]:
        cnt += 1
        D[i] = (arr[i], cnt)
    # 작으면
    else:
        D[i] = D[i-1]

print(D[N-1][1])

그러나 수열이 증가되지 않는 부분에서 정보를 바꿔버린다면

그 원소를 기점으로 새로운 증가수열이 나올 수도 있는데 그렇게 만들 수 없게 된다.

따라서 올바른 풀이와 코드는 다음과 같다.

DP리스트에 길이정보를 저장하는데, i번째까지 반복하는 문을 추가로 돌려,

이전 i번째 전까지의 원소들보다 i번째 원소가 클 경우에만 부분수열 길이정보를 갱신한다.

그렇게 해야 각 인덱스에 있는 원소들 전부 부분수열을 만들 수 있다.

코드

N = int(input())
arr = list(map(int, input().split()))
D = [1] * N

for i in range(1, N):
    for j in range(0, i):
        if arr[i] > arr[j]:
            D[i] = max(D[i], D[j] + 1)

print(max(D))

문제링크

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

문제설명

6
6
10
13
9
8
1

33

문제풀이

계단오르기 문제랑 점화식을 세우는 과정이 상당히 흡사했다.

https://baegopeun-sj.tistory.com/84

이유는 세 잔을 연속해서 마실 수 없다는 조건이 같기 때문이다.

단지, 최댓값을 저장하기 위해 경우들을 비교하는 과정에서 D[i-1]또한 고려해야 하는 것이 추가됐다.

D[i]의 정의를 i번째 잔까지 조건대로 마시면서 마실 수 있는 최대량으로 한다면,

i >=3 일때

D[i] = max(D[i-2]+arr[i], D[i-3]+arr[i-1]+arr[i], D[i-1])

이 되겠다.

코드

N = int(input())
D = [0] * N
arr = [int(input()) for _ in range(N)]

if N < 3:
    print(sum(arr))
else:
    D[0] = arr[0]
    D[1] = arr[0] + arr[1]
    D[2] = max(arr[0]+arr[2], arr[1]+arr[2], D[1])
    for i in range(3, N):
        D[i] = max(D[i-2]+arr[i], D[i-3]+arr[i-1]+arr[i], D[i-1])
    
    print(D[N-1])

문제링크

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

문제설명

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

30

문제풀이

생각보다 점화식을 빨리 작성할 수 있었던 것 같다.

나올 수 있는 n의 범위가 500까지 이므로 O(n^2)이라 해도 시간복잡도 걱정은 없다.

dp리스트 또한 이차원 리스트로 나타내기 위해,

이중 for문을 사용했고,

DP리스트의 각 원소를 점화식을 통해 갱신하였다.

점화식은 다음과 같다.

(0 < j < 각 줄의 리스트크기 - 1) 의 경우

D[i][j] = arr[i][j] + max(D[i-1][j-1] + D[i-1][j])

그리고 j가 양 끝 인덱스인 0 혹은 M-1의 경우,

그 이전 줄의 양 끝 인덱스에 있는 DP리스트 값을 현재원소와 더하기만 하면 된다.

코드

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
D = [[0 for j in range(len(arr[i]))] for i in range(N)]

D[0] = arr[0]

# DP 트리 채우기
for i in range(1, N):
    M = len(arr[i])
    for j in range(M):
        if 0 < j < M-1:
            D[i][j] = arr[i][j] + max(D[i-1][j-1], D[i-1][j])
        elif j == M-1:
            D[i][j] = arr[i][j] + D[i-1][j-1]
        elif j == 0:
            D[i][j] = arr[i][j] + D[i-1][j]

# N-1번째 dp리스트에 있는 리스트에서 최댓값 구하면 됨.
print(max(D[N-1]))

문제링크

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

문제설명

3
26 40 83
49 60 57
13 89 99

96

문제풀이

점화식을 세워보려 했지만 잘 떠오르지 않은 문제였다.

이 문제는 DP리스트를 이차원리스트로 만들어,

색상 별로 누적된 각 최솟값을 각각 저장을 해 가는 것이 핵심이다. 

즉, D[i] 란 i번째 집까지 누적된 최소비용을 색상별로 메모한 리스트가 되겠다.

점화식을 세워보면

D[n][색상1] = arr[n][색상1] + min(D[n-1][색상2], D[n-1][색상3])

이런식으로 각각 RGB 모두 점화식을 세우면 된다.

코드

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
D = [[0 for _ in range(N)] for _ in range(N)]

# D[i] : i번째 집까지 누적된 최소비용을 색상별로 메모한 리스트
# D[i][0] - 빨강,  D[i][1] - 초록, D[i][2] - 파랑
D[0][0] = arr[0][0]
D[0][1] = arr[0][1]
D[0][2] = arr[0][2]

for i in range(1, N):
    D[i][0] = arr[i][0] + min(D[i-1][1], D[i-1][2])  # 빨간색
    D[i][1] = arr[i][1] + min(D[i-1][0], D[i-1][2])  # 초록색
    D[i][2] = arr[i][2] + min(D[i-1][0], D[i-1][1])  # 파란색

print(min(D[N-1][0], D[N-1][1], D[N-1][2]))
# 점화식 
# D[n][색상1] = arr[n][색상1] + min(D[n-1][색상2], D[n-1][색상3])

문제설명

여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다.

각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.

이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.

따라서 개미 전사가 정찰병에서 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.

개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

[입력 조건]

1. 첫째 줄에 식량창고의 개수 N이 주어집니다. (3 <= N <= 100)

2. 둘째 줄에 공백을 기준으로 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 <= K <= 1,000)

[출력 조건]

첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오

문제풀이

D[i] 는 i번째까지의 최적의 해를 메모이제이션을 통해 저장한 것이다.

즉, 털 수 있는 식량의 최댓값이 저장됨을 의미한다.

점화식을 도출해보면,

D[i] = max(D[i-1], D[i-2]+arr[i]) 가 된다. (2<= i < N 일 경우)

코드

N = int(input())
arr = list(map(int, input().split()))
D = [0] * 1001

D[0] = arr[0]
D[1] = max(D[0], arr[1])

for i in range(2, N):
    D[i] = max(D[i-1], D[i-2] + arr[i])

print(D[N-1])

문제링크

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

문제설명

문제풀이

전형적인 다이나믹 프로그래밍 문제이다.

역시나 점화식만 찾아내면 쉽게 풀 수 있으나, 그 과정이 매우 어려운 것 같다.

점화식을 세울때 다음을 고려하면 그나마 쉽게 세울 수 있을거라 한다.

DP테이블의 첫번째, 두번째 요소에 대해 세번째를 어떻게 만족시킬지, 그리고 그것이 네번째까지 보장을 해주는지에 집중하자. 

D[i] 의미: i번째 계단에 오기까지의 얻을수있는 점수 최댓값.

일단 조건중에 3개 연속으로 계단을 밟을 수 없다 했으므로

N이 2개 이하일 경우에는 전체 점수배열의 합을 출력하자.

만약 3개 이상일 경우에 점화식은 다음과 같다.

D[i] = max(D[i-3]+arr[i-1]+arr[i], D[i-2]+arr[i])

두가지 상황에서 나올수있는 값의 최댓값이 D[i] 라는 얘기인데,
★이는 i-1번째 계단을 밟고 올 경우와, i-1번째 계단을 밟지 않고 건너올 경우를 나눈 것이다.

(i=4) 일때를 보자

다음에 4의 위치로 건너올 수 있는 계단위치는 2와 3이다.

그러므로,

1. (2까지의 최댓값 + 4번째 계단점수) => D[i-2] + arr[i]

2. (1까지의 최댓값 + 3번째 계단점수 + 4번째 계단점수) => D[i-3] + arr[i-1] + arr[i]

이 둘의 최댓값이 D[i]가 되어야 한다.

코드

N = int(input())
arr = [0] * (N+1)
D = [0] * (N+1)
for i in range(1, N+1):
    data = int(input())
    arr[i] = data

# 계단이 2개이하인 경우
if N <= 2:
    print(sum(arr))

# 계단이 3개이상인 경우 (세개 연속해서 못밟으므로)
else:
    D[1] = arr[1]
    D[2] = arr[1] + arr[2]
    for i in range(3, N+1):
        D[i] = max(D[i-3]+arr[i-1]+arr[i], D[i-2]+arr[i])
    print(D[N])

문제링크

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

문제설명

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

문제풀이

섬의 개수 즉, 구역 수가 몇개냐를 묻는 문제가 되겠다.

적록색약문제라든지, 유기농배추 문제라든지 여러 다른 BFS문제와 흡사한 방법으로 풀면 쉽게 해결된다.

다만,

1. 인접한 구역의 조건이 4방향이 아닌 대각선 방향까지 고려하여 8방향인 점

2. 테스트케이스의 개수가 주어지지 않고 0 0을 입력받으면 종료해야 하는점.

을 염두에 두자.  => 입력을 무한정 받다가, 조건에 부합하면 탈출할수 있도록 하자.  cf. [백준 1686] 복날

코드

# 섬의개수를 출력
# 1은 Land, 0은 바다
# BFS를 통해 구역수를 세는 문제 (같은 구역이 되려면 가로 혹은 세로 혹은 대각선 으로 인접해야함)
from collections import deque

dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, -1, 1, 1, -1, -1, 1]

def BFS(x, y):
    queue = deque([(x, y)])
    visited[x][y] = 1

    while queue:
        curX, curY = queue.popleft()

        for i in range(8):
            nx = curX + dx[i]
            ny = curY + dy[i]
            # 인덱스범위안에 있고 땅이고 방문하지 않았으면 방문
            if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1 and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = 1

while True:
    try:
        data = input()
        if data == '0 0' or not data:
            break
        w, h = map(int, data.split())
        graph = [[0 for _ in range(w)] for _ in range(h)]

        for i in range(h):
            graph[i] = list(map(int, input().split()))

        cnt = 0
        visited = [[0 for _ in range(w)] for _ in range(h)]
        # 구역 개수 구하기        
        for i in range(h):
            for j in range(w):    
                # 땅이고 방문하지 않은 노드면 방문.
                if graph[i][j] == 1 and not visited[i][j]:
                    BFS(i, j)
                    # 한번의 BFS끝날때마다 구역수 1증가
                    cnt += 1
        print(cnt)

    except:
        break

문제링크

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

문제설명

문제풀이

입력받기도 생각보다 까다롭고 조건이 까다로워서 생각보다는 헤맸던것 같다.

실제 코딩테스트에서 나온다면 시간안에 풀 수 있을지 의문이다...

우선 처음 시도했을 때의 생각은,

딕셔너리의 키: 벨류 쌍으로

# 형식 
# {
#     ('팀이름', 인원수): ['멤버1','멤버2', ...]
#   }

이런 형태로 집어넣으면 되겠거니 생각했다.

하지만 이것보다는 다음의 핵심을 활용하자.

★핵심

- 딕셔너리를 두개 사용하자 (왜 이 생각을 못했을까..)

코드

# N 걸그룹수, M 퀴즈수
N, M = map(int, input().split())
dict1 = {} # {'팀이름' : ['멤버이름','멤버이름', ...] }
dict2 = {} # 

# 걸그룹 데이터 전부 입력완료
for i in range(N):
    team = input()
    num = int(input())
    dict1[team] = []
    for _ in range(num):
        name = input()
        dict1[team].append(name)
        dict2[name] = team

for _ in range(M):
    quiz = input()
    type = int(input())

    # 타입이 1이라면 멤버의 소속팀 출력
    if type:
        print(dict2[quiz])
    # 0이라면 팀의 소속멤버 모두 출력
    else:
        memberArr = sorted(dict1[quiz])
        for member in memberArr:
            print(member)