정답 코드 및 설명

정답 전체 코드

from collections import deque

def bfs(start, grid, size, n):
    # 방향 벡터 설정 (상, 좌, 우, 하)
    directions = [(-1, 0), (0, -1), (0, 1), (1, 0)]
    # BFS를 위한 큐 초기화 및 시작점 등록
    queue = deque([(start[0], start[1], 0)])  # (row, col, distance)
    # 방문 체크 배열 초기화
    visited = [[False] * n for _ in range(n)]
    visited[start[0]][start[1]] = True
    # 먹을 수 있는 물고기 리스트
    eatable_fish = []

    # BFS 실행
    while queue:
        r, c, dist = queue.popleft()

        # 가능한 모든 방향으로 탐색
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
                if grid[nr][nc] <= size:  # 이동 가능 조건
                    visited[nr][nc] = True
                    if 0 < grid[nr][nc] < size:  # 먹을 수 있는 물고기 조건
                        eatable_fish.append((dist + 1, nr, nc))
                    queue.append((nr, nc, dist + 1))

    # 먹을 수 있는 가장 가까운 물고기 반환
    if eatable_fish:
        eatable_fish.sort()
        return eatable_fish[0]
    return None

n = int(input().strip())
grid = [list(map(int, input().split())) for _ in range(n)]

shark_size = 2 #초기 아기 상어 사이즈
eaten = 0 #먹은 물고기 수 
time = 0 #총 지난 시간 

#아기 상어 초기 위치 찾기
shark_pos = None
for i in range(n):
    for j in range(n):
        if grid[i][j] == 9:
            shark_pos = (i,j)
            grid[i][j] = 0 #상어 위치 초기화
            break
    if shark_pos:
        break

while True: #먹을 수 있는 물고기가 없을 때 까지 반복
    result = bfs(shark_pos, grid, shark_size, n)
    if not result:
         break
    dist, fish_r, fish_c = result
    # 물고기 먹기
    grid[fish_r][fish_c] = 0
    shark_pos = (fish_r, fish_c)
    time += dist
    eaten += 1

    # 성장 조건 체크
    if eaten == shark_size:
        shark_size += 1
        eaten = 0

print(time)

문제 설명

NxN 크기의 격자에서 아기 상어가 물고기들과 함께 있다. 아기 상어는 초기 크기가 2이며, 이동하면서 자신보다 작은 크기의 물고기만 먹을 수 있다. 상어는 자신의 크기만큼 수의 물고리를 먹으면 크기가 1증가하고 크기가 같은 물고기는 먹지 못하지만 해당 칸을 지나갈 수 있다. 이 문제의 목표는 아기 상어가 더 이상 먹을 수 있는 물고기가 없을 때까지 걸리는 시간을 구하는 것이다.

이 문제를 풀기 위해선 아기 상어의 현재 위치에서 출발해서 먹을 수 있는 물고기들의 위치를 찾아가는 최단 경로를 계산해야한다. 각 칸을 방문하면서 아기 상어가 이동할 있는 지와 먹을 수 있는 물고기가 있는 지 확인한다.

코드 설명

n = int(input().strip())
grid = [list(map(int, input().split())) for _ in range(n)]

shark_size = 2 #초기 아기 상어 사이즈
eaten = 0 #먹은 물고기 수 
time = 0 #총 지난 시간 

#아기 상어 초기 위치 찾기
shark_pos = None
for i in range(n):
    for j in range(n):
        if grid[i][j] == 9:
            shark_pos = (i,j)
            grid[i][j] = 0 #상어 위치 초기화
            break
    if shark_pos:
        break

먼저 n 과 격자 데이터를 입력 받는다. 초기 사이즈, 먹은 물고기, 시간을 저장할 변수를 초기화 한다.

현재 입력 데이터로 바로 아기 상어 초기 위치를 알 수 없으니 9 가 있는 칸의 i,j 를 알아낸다.

def bfs(start, grid, size, n):
    # 방향 벡터 설정 (상, 좌, 우, 하)
    directions = [(-1, 0), (0, -1), (0, 1), (1, 0)]
    # BFS를 위한 큐 초기화 및 시작점 등록
    queue = deque([(start[0], start[1], 0)])  # (row, col, distance)
    # 방문 체크 배열 초기화
    visited = [[False] * n for _ in range(n)]
    visited[start[0]][start[1]] = True
    # 먹을 수 있는 물고기 리스트
    eatable_fish = []

    # BFS 실행
    while queue:
        r, c, dist = queue.popleft()

        # 가능한 모든 방향으로 탐색
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
                if grid[nr][nc] <= size:  # 이동 가능 조건
                    visited[nr][nc] = True
                    if 0 < grid[nr][nc] < size:  # 먹을 수 있는 물고기 조건
                        eatable_fish.append((dist + 1, nr, nc))
                    queue.append((nr, nc, dist + 1))

    # 먹을 수 있는 가장 가까운 물고기 반환
    if eatable_fish:
        eatable_fish.sort()
        return eatable_fish[0]
    return None

시작점을 기준으로 탐색을 실행한다. 각 칸에 대해서 상하좌우로 이동 가능한지 확인한다. 이동 가능한 칸 중에서 아기 상어가 먹을 수 있는 칸을 찾으면 그 위치와 이동에 필요한 거리를 저장한다. 먹을 수 있는 물고기 중 가장 가까운 것을 반환하고, 여러 마리 일 경우 가장 위에, 왼쪽에 있는 물고기를 선택한다.

while True: #먹을 수 있는 물고기가 없을 때 까지 반복
    result = bfs(shark_pos, grid, shark_size, n)
    if not result:
         break
    dist, fish_r, fish_c = result
    # 물고기 먹기
    grid[fish_r][fish_c] = 0
    shark_pos = (fish_r, fish_c)
    time += dist
    eaten += 1

    # 성장 조건 체크
    if eaten == shark_size:
        shark_size += 1
        eaten = 0

먹을 수 있는 물고기가 없을 때까지 bfs 함수를 통해서 먹을 수 있는 물고기를 찾고 그 위치로 이동 시키고 물고기를 먹는다. 이때 아기 상어가 자신의 크기 만큼 물고기를 먹으면 크기를 증가 시킨다.

그 후 총 소요된 시간을 기록한다.

print(time)

총 소요된 시간을 출력하면 정답이 된다.

정답 코드 및 문제 설명

정답 전체 코드

n = int(input()) # 교실 크기 
data = [[0] * n for _ in range(n)] # 교실 격자 초기화 
students = [list(map(int, input().split())) for _ in range(n**2)] # 각 학생과 좋아하는 학생 4명 번호 저장

#상하 좌우 움직일때 좌표 미리 저장
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for student in students:
    available = []
    for i in range(n):
        for j in range(n):
            if data[i][j] == 0: #현재 선택 격자가 비었다면
                # 각 칸마다 좋아하는 학생수, 빈자리 수를 계산
                prefer, empty = 0, 0
                for k in range(4):
                    nx, ny = i + dx[k], j + dy[k]
                    if 0 <= nx < n and 0 <= ny < n:
                        if data[nx][ny] in student[1:]:
                            prefer += 1
                        if data[nx][ny] == 0:
                            empty += 1
                #계산된 결과를 available 리스트에 저장된다.
                available.append([i,j,prefer,empty])
    #계산된 결과를 정렬
    #좋아하는 학생 수(내림차순), 빈 칸 수(내림차순), 행 번호(오름차순), 열 번호(오름차순)      
    available.sort(key=lambda x: (-x[2], -x[3], x[0], x[1]))  
    #최적의 자리에 학생 번호를 배치한다.   
    data[available[0][0]][available[0][1]] = student[0]

answer = 0
#만족도 점수 배열 0~4명 좋아하는 학생 수에 따라 다음
score = [0,1,10,100,1000]
students.sort()
for i in range(n):
    for j in range(n):
        count = 0
        for k in range(4):
            #인접한 좌표를 돌면서 좋아하는 학생 수 판별 
            nx, ny = i + dx[k], j + dy[k] 
            if 0 <= nx < n and 0 <= ny < n: 
                if data[nx][ny] in students[data[i][j] - 1][1:]:
                    count += 1
        answer += score[count] 
print(answer)

문제 및 코드 설명

문제에는 아래 3가지 조건을 순서대로 우선순위를 가진다.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

즉, 좋아하는 학생이 인접한 칸에 얼마나 있는지, 인접한 칸 중 빈칸, 행, 열 순으로 정렬해야한다.

available.sort(key=lambda x: (-x[2], -x[3], x[0], x[1]))

코드 내에 sort 가 쓰인 부분을 보면 알 수 있다. available 리스트는 각 학생마다 [행 , 열, 좋아하는 학생 수, 인접한 빈칸 수] 로 저장되어있다.

람다 함수를 사용하여 우선 순위를 설정하여 sort, 정렬할 수 있다. x: -x[2] 와 같이 - 가 붙어있으면 내림 차순으로, x[0] 처럼 붙어있지 않다면 해당하는 것을 오름차순으로 정렬한다.

즉, 위 코드는 좋아하는 학생 수 x[2] 를 내림차순으로 먼저 정렬하고, 인접한 빈칸 수 x[3] 을 내림차순으로 그 다음으로 행 과 열 을 오름차순으로 정렬한다.

코드 및 설명

정답 전체코드

import sys
from collections import defaultdict
input = sys.stdin.read
# 모든 입력을 받기
data = input().split()

index = 0 
N = int(data[index])
M = int(data[index + 1])
K = int(data[index + 2])
index += 3
A = []
for i in range(N):
    A.append(list(map(int, data[index:index + N])))
    index += N

tree_info = []
for j in range(M):
    x = int(data[index])
    y = int(data[index + 1])
    z = int(data[index + 2])
    tree_info.append((x, y, z))
    index += 3

# 입력 잘됬는지 확인하는 출력
# print("N, M, K =", N, M, K)
# print("A[r, c] =")
# for row in A:
#     print(row)
# print("심을 나무의 정보를 담은 배열:")
# for info in tree_info:
#     print("(x, y, z) =", info[0], info[1], info[2])

# 나무 정보를 관리하기 위해 딕셔너리로 만들자
# 키는 위치로 (x,y), 값 : x,y 위치에 있는 나무 나이 리스트
# 나무 정보를 관리할 defaultdict 사용, 나무를 위치별로 그룹화
trees = defaultdict(list)
for x, y, age in tree_info:
    trees[(x - 1, y - 1)].append(age)

# 나무 리스트를 나이순으로 정렬
for pos in trees:
    trees[pos].sort()

# 초기 양분 배열 설정, 모든 칸에 양분 5
nutrients = [[5] * N for _ in range(N)]

# 나무 번식 방향 설정, 8방향
directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

for _ in range(K):
    # 각 계절의 작업을 시작, 봄에서 죽은 나무를 여름에 양분으로 변환
    dead_trees = defaultdict(int)
    for pos in list(trees):
        alive = []
        dead = 0
        for age in trees[pos]:
            if nutrients[pos[0]][pos[1]] >= age:
                nutrients[pos[0]][pos[1]] -= age
                alive.append(age + 1)
            else:
                dead += age // 2
        trees[pos] = alive
        nutrients[pos[0]][pos[1]] += dead

    # 가을에는 번식 가능한 나무가 인접 칸에 새로운 나무를 생성
    new_trees = defaultdict(list)
    for pos, ages in trees.items():
        for age in ages:
            if age % 5 == 0:
                for dx, dy in directions:
                    nx, ny = pos[0] + dx, pos[1] + dy
                    if 0 <= nx < N and 0 <= ny < N:
                        new_trees[(nx, ny)].append(1)

    # 새로운 나무를 기존 리스트에 추가하고 정렬
    for pos, new_ages in new_trees.items():
        trees[pos].extend(new_ages)
        trees[pos].sort()

    # 겨울에 각 칸에 양분 추가
    for i in range(N):
        for j in range(N):
            nutrients[i][j] += A[i][j]

# K년 후 살아있는 나무의 총 수 계산
live_tree_count = sum(len(ages) for ages in trees.values())
print(live_tree_count)

문제 설명

위 문제는 복잡해보이지만 내용만 이해하면 쉽다. 나무 재테크

부동산 투자로 돈 벌어서 N x N 크기의 땅 구매함. 쉬운 땅 관리를 위해서 땅을 1 x 1 로 나누어 놓았음. 각 칸의 좌표는 (r, c) 로 나타낸다. r 은 가장 위에서부터 떨어진 칸의 갯수 c 는 가장 왼쪽으로부터 떨어진 칸의 갯수 r과 c는 1부터 시작한다. 땅의 양분을 조사하는 로봇으로 1 x 1 크기의 칸에 들어있는 양분 조사 모든 칸에 대해서 조사를 한다. 가장 처음엔 양분은 모든 칸에 5만큼 들어있다.

이 땅에 나무를 심고 키워서 파는 나무 재테크를 할 것이다. M 개의 나무를 구매해서 심었다. 같은 1 x 1 크기의 칸에 여러 개의 나무가 심어져 있을 수도 있다. 나무는 사계절을 보낸다.

1. 봄 나무가 자신의 나이만큼 양분을 먹고 나이가 1증가한다. 각각의 나무는 자기가 있는 1 x 1 칸의 양분만 먹는다. 하나의 칸에 여러 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해서 자신의 나이만큼 먹을 수 없다면 즉시 죽는다.

2. 여름 봄에 죽은 나무가 양분으로 변한다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다

3. 가을 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야하며, 인접한 8개의 칸에는 나이가 1인 나무가 생긴다. 어떤 칸 (r,c) 와 인접한 칸인 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 이다. 땅을 벗어나는 칸에는 나무가 생기지 않는다.

4. 겨울 로봇이 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c] 이며 입력으로 주어진다.

K 년이 지난 후 땅에 살아있는 나무 갯수를 구하는 프로그램을 작성하여라.

입력으로 첫째 줄에는 N, M, K 가 주어진다. 각각은 땅의 크기, 심는 나무 갯수, 어느 년도가 지났는 가 둘째 줄부터 N개의 줄에 A 배열의 값이 주어진다. r번째 줄의 c번째 값은 A[r][c] 이다. 이는 r,c 칸에 겨울에 줄 양분이다. 다음 M개의 줄에는 심은 나무의 정보를 나타내는 세 정수 x,y,z가 주어진다. x, y 는 나무를 심을 위치, z 는 나이를 의미한다.

코드 설명

import sys
from collections import defaultdict
input = sys.stdin.read

입력을 받기 위한 input 을 시간 제한에 맞추기 위해서 sys 를 import 하고 input 을 sys.stdin.read 로 지정한다.

data = input().split()

index = 0 
N = int(data[index])
M = int(data[index + 1])
K = int(data[index + 2])
index += 3
A = []
for i in range(N):
    A.append(list(map(int, data[index:index + N])))
    index += N

tree_info = []
for j in range(M):
    x = int(data[index])
    y = int(data[index + 1])
    z = int(data[index + 2])
    tree_info.append((x, y, z))
    index += 3

read 를 사용해서 한번에 다 받고 나눠준다.

# 나무 정보를 위치별로 저장하고 관리
trees = defaultdict(list)
for x, y, age in tree_info:
    trees[(x - 1, y - 1)].append(age)

defaultdict(list) 를 사용해서 심을 나무의 정보들을 저장할 것이다. defaultdict은 Python의 collection 모듈에 있는 특수한 딕셔너리이다. 기본적인 python 표준 dict 딕셔너리와 비슷한데 defaultdict 은 키에 대한 기본 값을 제공하는 기능이 추가되어있다. 키에 대한 값이 없을 때, 지정한 기본값을 자동으로 생성하여 반환한다.

defaultdict(list)를 사용하는 이유는 각 위치 (x, y)에 대해 여러 나무 객체를 관리해야 하기 때문에 사용한다. 나무가 심어지지 않은 위치에 처음 접근할때 자동으로 빈 리스트를 할당하기에 나무를 추가할 때 쉽게 처리할 수 있다.

# 나무 리스트를 나이순으로 정렬
for pos in trees:
    trees[pos].sort()

# 초기 양분 배열 설정
nutrients = [[5] * N for _ in range(N)]

# 나무 번식 방향 설정
directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

trees 를 나이순으로 정렬하고, 초기 양분 배열을 설정한다. 나무가 번식하는 것은 그 나무를 중심으로 하는 3x3 칸으로 나무가 증식하는 데, 이때 자신을 제외한다. 번식을 계산하기 위해서 방향을 모두 저장해놓는다.

for _ in range(K):
    # 봄과 여름 작업
    dead_trees = defaultdict(int)
    for pos in list(trees):
        alive = []
        dead = 0
        for age in trees[pos]:
            if nutrients[pos[0]][pos[1]] >= age:
                nutrients[pos[0]][pos[1]] -= age
                alive.append(age + 1)
            else:
                dead += age // 2
        trees[pos] = alive
        nutrients[pos[0]][pos[1]] += dead

먼저, 봄과 여름작업을 해준다.

죽을 나무를 저장할 변수, dead_trees를 deaultdict(int)으로 만든다. trees(지금 심어진 모든 나무) 의 위치 마다 alive = [] 살아있는 나무 저장배열, dead 죽을 나무 수 저장한다. trees 위치마다 나이를 가져와서 양분을 뺀다. 양분을 먹을 수 있다면 나이를 1증가시키고, 양분을 먹을 수 없다면 나이의 2분의 1을 dead 변수에 저장한다. trees[pos] 를 alive 로 바꿔준다. 양분에 dead 만큼 더 넣어준다.

    # 가을 작업
    new_trees = defaultdict(list)
    for pos, ages in trees.items():
        for age in ages:
            if age % 5 == 0:
                for dx, dy in directions:
                    nx, ny = pos[0] + dx, pos[1] + dy
                    if 0 <= nx < N and 0 <= ny < N:
                        new_trees[(nx, ny)].append(1)

    # 새로운 나무를 기존 리스트에 추가하고 정렬
    for pos, new_ages in new_trees.items():
        trees[pos].extend(new_ages)
        trees[pos].sort()

가을에는 나이가 5의 배수인 나무를 찾아서 directions 의 배열을 사용해서 각각에 나무를 심는다. 그 후 다시 정렬해준다. 내년을 위해서

    # 겨울 작업
    for i in range(N):
        for j in range(N):
            nutrients[i][j] += A[i][j]

겨울에는 양분을 더해준다.

# K년 후 살아있는 나무의 총 수 계산
live_tree_count = sum(len(ages) for ages in trees.values())
print(live_tree_count)

trees 는 각 위치를 키로 해당 위치에 살아있는 나무의 나이들을 요소로 갖는 리스트이니까 trees.values() 는 딕셔너리의 모든 값(각 위치의 나무 나이 리스트)들을 반환한다. 즉, 각 리스트는 해당 위치에 살아있는 나무들의 나이를 포함한다.

sum(len(ages) for ages in trees.values()) 은 sum 함수를 사용해서 각 위치의 나무 리스트의 길이를 합산한다.

len(ages) 는 특정 위치의 나무 리스트의 길이, 그 위치에서 살아있는 나무의 수를 나타낸다.

for ages in trees.values()는 trees 딕셔너리의 각 값(나무 리스트)에 대해 반복하며, 각 위치에서의 나무 수(리스트의 길이)를 계산한다.

sum() 함수는 이 반복을 통해 얻은 각 위치의 나무 수들을 모두 더하여 총 나무 수를 반환한다.

따라서, sum(len(ages) for ages in trees.values())는 모든 위치의 나무 리스트들의 길이를 합산하여, 전체 나무 재테크 땅에서 살아남은 나무의 총 수를 계산한다.

전체 정답 코드 및 설명

정답 코드

import sys
input = sys.stdin.read

# 입력 받기
data = input().split()
N = int(data[0])  # 시험장의 개수
A = list(map(int, data[1:N+1]))  # 각 시험장의 응시자 수
B, C = map(int, data[N+1:])  # B: 총감독관 감시 가능 인원, C: 부감독관 감시 가능 인원

# 결과 계산
result = N  # 각 시험장마다 최소 1명의 총감독관 필요
for i in range(N):
    remaining = A[i] - B  # 총감독관이 감시 후 남은 응시자 수
    if remaining > 0:  # 남은 응시자가 있으면 부감독관 배치
        result += (remaining + C - 1) // C 

# 결과 출력
print(result)

문제 설명

각 시험장에 꼭 1명의 총감독이 있어야한다. 이 점을 주의하자.

1번째 풀이

import sys
input = sys.stdin.readline

# 시험장의 개수 1 <= N <= 1,000,000
N = int(input())
# A[i] 는 각 시험장에 있는 응시자의 수
A = list(map(int, input().strip().split()))
# B : 총감독관이 한 시험장에서 감시할 수 있는 응시자 수 
# C : 부감독관이 한 시험장에서 감시할 수 있는 응시자 수 
B, C = map(int, input().strip().split()) 

# 각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수 출력
result = N # 각 시험장에 총감독관이 들어가야함 
for i in range(N):
    A[i] -= B # 각 시험장에 총감독관이 체크할 수 있는 인원 제외시키기
for i in range(N):
    temp = A[i]
    while temp > 0:
        # print("(3) temp = ", temp, "i = ", i, "result = ", result)
        temp = temp - C
        result = result + 1
        # print("(4) temp = ", temp, "i = ", i, "result = ", result)

print(result)

처음에 모든 값을 입력 받고, 각 시험장에 총 감독관을 배치해야하기 때문에 result 결과값을 가지는 변수를 N(시험장 수) 로 설정하였고, 각 시험장에 총감독관이 감독할 수 있는 인원수를 빼주었다.

그 후에 A 배열을 하나씩 순회하였다. 순회할 때마다 temp 가 0보다 크다면 temp 에 C 를 빼주고 result 값에 +1 해주었다.

이 경우 시간 초과라는 결과로 문제 풀이에 실패하였다.

2번째 풀이

import sys
input = sys.stdin.readline

# 시험장의 개수 1 <= N <= 1,000,000
N = int(input())
# A[i] 는 각 시험장에 있는 응시자의 수
A = list(map(int, input().strip().split()))
# B : 총감독관이 한 시험장에서 감시할 수 있는 응시자 수 
# C : 부감독관이 한 시험장에서 감시할 수 있는 응시자 수 
B, C = map(int, input().strip().split()) 
# print("처음 A : ",A)
# 각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수 출력
result = N # 각 시험장에 총감독관이 들어가야함 
for i in range(N):
    A[i] -= B # 각 시험장에 총감독관이 체크할 수 있는 인원 제외시키기
# print("총 감독관이 볼 수 있는 응시자 수를 뺌",A, "result = ", result)
for i in range(N):
    temp = A[i]
    q, r = divmod(temp, C)
    result += q
    if r > 0:
        result += 1

print(result)

1번째 풀이와 다른 점은 temp 를 C로 나누고 몫을 result에 더한 후 나머지가 존재하다면 +1 해주는 방법으로 풀었다. 하지만 제출 결과 틀렸습니다 가 나왔고, 확인을 위해서 모든 예제를 넣어보았지만 정답이 나왔기 때문에 어디가 잘못되었는 지 몰라 코드를 다시 리팩토링을 진행하였다.

3번째 풀이(정답)

import sys
input = sys.stdin.read

# 입력 받기
data = input().split()
N = int(data[0])  # 시험장의 개수
A = list(map(int, data[1:N+1]))  # 각 시험장의 응시자 수
B, C = map(int, data[N+1:])  # B: 총감독관 감시 가능 인원, C: 부감독관 감시 가능 인원

# 결과 계산
result = N  # 각 시험장마다 최소 1명의 총감독관 필요
for i in range(N):
    remaining = A[i] - B  # 총감독관이 감시 후 남은 응시자 수
    if remaining > 0:  # 남은 응시자가 있으면 부감독관 배치
        result += (remaining + C - 1) // C  # 필요한 부감독관 수: 올림 처리

# 결과 출력
print(result)

1. read 로 입력된 것을 모두 읽고, N 와 A, B, C 를 나누었다.
2. result 를 N 으로 설정한다. 각 시험장에 총 감독관을 한명씩 배치한 것이다.
3. 다음으로 for 문을 이용해 A 배열을 순회한다.
4. for 문 내에서 총감독관이 감시 할 수 있는 인원 수를 빼고 남은 응시자가 있을 경우 result 에 (남아 있는 수 // 부감독관이 감시 할 수 있는 인원) 값을 더해주는 데 이는 나머지가 있을 경우를 대비하여 남아 있는 수에 부감독관이 감시할 수 있는 인원 - 1 값을 더하고 나누었다.

총감독관이 들어가고도 인원수가 남을 경우 <<< 이 경우에 음수일 경우를 고려하지 않은 것.

정답 전체 코드

import sys
input = sys.stdin.readline

def cal_diff(start_team, link_team):
    start_power = sum([S[i][j] for i in start_team for j in start_team])
    link_power = sum([S[i][j] for i in link_team for j in link_team])
    return abs(start_power - link_power)

def backtrack(index, team):
    global min_diff
    if len(team) == n // 2:
        start_team = team
        link_team = [x for x in range(n) if x not in start_team]
        diff = cal_diff(start_team, link_team)
        min_diff = min(min_diff, diff)
        return 
    for i in range(index, n):
        if i not in team:
            team.append(i)
            backtrack(i +1, team)
            team.pop()

n = int(input())
S = [list(map(int, input().split())) for _ in range(n)]

min_diff = float('inf')

backtrack(0, [])

print(min_diff)

문제 설명

위 문제는 주어진 N명의 사람들을 두 팀으로 나누어, 각 팀의 능력치 차이를 최소화하는 문제이다. N은 짝수이고, 각 사람들 사이의 능력치는 주어진 2차원 배열에 S에 저장한다.

문제 접근 방법

1. 모든 가능한 팀 조합을 만들기
2. 각 조합에 대해 스타트팀과 링크 팀의 능력치 차이를 계산하고, 이 차이를 최소로 하는 값을 찾아야한다.

위 2가지를 수행하기 위해서 백트래킹 알고리즘을 사용하여 모든 가능한 팀 조합을 전부 탐색할 수 있다. 백트래킹 알고리즘은 모든 가능한 경우의 수 중에서 해를 찾는 방법으로, 중간에 답이 아닐거같은 경우 이 방법을 바로 포기하는 방법이라서 즉, 되돌아가서 Backtrack 이라고 불린다.

알고리즘 설명

1. 차이 계산 함수 cal_diff 는 주어진 두 팀 조합의 각 팀 능력치를 계산하고 두 팀의 차이를 절대값으로 바꾸어 반환한다.

2. 백트래킹 함수에서 특정 인덱스에서 시작하여 가능한 모든 팀 조합을 생성하고, 팀이 N/2 으로 구성되었을 때, 스타트 팀과 링크 팀의 능력치 차이를 계산하고, 이 차이를 최솟값을 업데이트한다.

3. 전역 변수 min_diff 스타트 팀과 링크 팀의 능력치 차이의 최솟값을 저장한다. 초기합은 inf 로 무한대로 설정한다.

4. N과 S를 입력받고, backtrack 함수를 호출하여 모든 가능한 팀 조합을 전부 탐색한다. 마지막에 min_diff 를 출력한다.

코드 설명

• 첫째 줄에 N을 입력받고, 이후 N개의 줄에 걸쳐 2차원 배열 S를 입력받는다.
• cal_diff 함수는 두 팀의 인덱스 리스트를 인자로 받아, 해당 팀의 능력치를 계산하고 두 팀의 능력치 차이를 반환한다.
• backtrack 함수는 현재 인덱스와 현재까지 구성된 팀의 리스트를 인자로 받는다. 함수 내에서, 팀이 N/2명으로 채워지면 스타트 팀과 링크 팀의 능력치 차이를 계산하고 min_diff를 업데이트한다. 그렇지 않은 경우, 현재 인덱스부터 시작하여 다음 사람을 팀에 추가하고 백트래킹을 계속 진행한다.

결론

백 트래킹 방법을 사용함으로써 모든 팀 조합을 고려하여 스타트 팀과 링크 팀의 능력치 차이를 최소화할 수 있는 최적의 팀 조합을 찾을 수 있었다. 백트래킹을 통해서 모든 가능한 경우를 탐색하는 브루트포스 방식의 문제로, 조합론적 접근과 최적화를 요구하는 문제이다.

백트래킹 알고리즘이 무엇인지, 어떻게 사용하는 건지에 익숙해지는 문제 등을 풀면 쉽게 풀 수 있다.

정답 전체 코드

import sys

#연산하는 함수
def calculate(op, a, b):
    if op == '+':
        return a + b
    elif op == '-':
        return a - b
    elif op == '*':
        return a * b
    elif op == '/':
        # 음수 나눗셈 처리
        if a * b < 0 and a % b != 0:
            return a // b + 1
        return a // b

# 백트래킹
def backtrack(index, current_result):
    global addition_count, subtraction_count, multiplication_count, division_count

    if index == n:
        results.add(current_result)
        return

    if addition_count > 0:
        addition_count -= 1
        backtrack(index + 1, calculate('+', current_result, input_arr[index]))
        addition_count += 1

    if subtraction_count > 0:
        subtraction_count -= 1
        backtrack(index + 1, calculate('-', current_result, input_arr[index]))
        subtraction_count += 1

    if multiplication_count > 0:
        multiplication_count -= 1
        backtrack(index + 1, calculate('*', current_result, input_arr[index]))
        multiplication_count += 1

    if division_count > 0:
        division_count -= 1
        backtrack(index + 1, calculate('/', current_result, input_arr[index]))
        division_count += 1    

input = sys.stdin.readline

n = int(input())
input_arr = list(map(int, input().strip().split()))

addition_count, subtraction_count, multiplication_count, division_count = map(int, input().strip().split())

results = set()

backtrack(1, input_arr[0])
print(max(results))
print(min(results))

문제 설명

위 문제는 N개의 수와 이 수들 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어졌을때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 문제이다. 사용할 수 있는 연산자는 덧셈, 뺄셈, 곱셉, 나눗셈의 네 가지이다. 문제의 핵심은 바로 주어진 수의 순서를 바꾸지 않으면서, 모든 가능한 연산자 조합을 시도하여 식의 결과값을 최대화하거나 최소화하는 것이다.

알고리즘 설명

위 문제를 해결하기 위해서 백트래킹 알고리즘을 사용한다. 백트래킹은 해를 찾아가는 도중에 해가 아니면 되돌아가서 다시 해를 찾아가는 기법이다. 이 문제에서는 각 단계에서 사용할 수 있는 연산자가 무엇인지에 따라 다음 단계로 진행하거나 되돌아간다.

1. 입력으로 주어진 수의 개수 N, 각 수를 담는 배열 input_arr, 그리고 각 연산자의 개수를 나타내는 네 개의 변수를 입력받을 준비를 한다.

2. 연산 함수는 두 수와 연산자를 입력으로 받아서 결과를 반환하는 calculate 함수를 정의한다. 이 함수는 네 가지 연산자에 대해 적절히 연산을 수행하며 특히 나누셈 연산 시 음수 나눗셈 처리에 적용한다.

3. 백트래킹 함수 실행한다. 처음에는 배열의 첫 번째 수를 시작 결과값으로 하고, backtrack 함수를 호출하여 모든 가능한 식을 탐색한다. 이 함수는 현재까지의 계산 결과와 처리할 다음 수의 인덱스(순서)를 매개변수로 받는다.

4. 가능한 모든 연산자에 대해 현재 수와 다음 수를 연산하고, 연산자 개수를 하나 줄인 후 다시 backtrack 함수를 호출한다. 모든 수를 처리한 후(즉, 인덱스가 N에 도달했을 떄) 현재까지의 계산 결과를 결과 set 에 추가한다.

5. 탐색이 끝나면 결과 집합에서 최댓값과 최소값을 찾아 출력한다.

코드 설명

• 입력을 받고 필요한 변수를 초기화한다. results 집합은 가능한 모든 결과를 저장한다.
• calculate 함수는 주어진 연산자에 따라 두 수의 연산 결과를 반환한다. 나눗셈 시 음수 처리를 위해 특별한 조건을 적용하기 위함이다.
• backtrack 함수는 현재 인덱스와 현재까지의 계산 결과를 인자로 받아, 가능한 모든 연산자를 적용하며 재귀적으로 다음 단계로 진행한다. 각 연산자를 사용할 때마다 해당 연산자의 개수를 줄이고, 재귀 호출이 끝난 후에는 다시 개수를 복원한다.
• 모든 수를 고려했을 때(즉, index == n일 때) 현재의 계산 결과를 results 집합에 추가한다.
• 최종적으로 results 집합에서 최대값과 최소값을 찾아 출력한다.

결론

이 문제를 해결하기 위해서 백트래킹 기법을 통해서 모든 가능한 연산자 조합을 시도하면서, 각 경우에 대해 계산된 결과를 추적하고, 그중 최댓값과 최솟값을 찾는 방식으로 해결할 수 있었다. 이러한 접근 방식은 가능한 모든 경우의 수를 고려하기 때문에, 문제의 조건 내에서 가장 좋은 결과를 도출할 수 있다.

문제 링크

정답 전체 코드

N = int(input())
T = []
P = []

for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)

DP = [0] * (N+1)

for i in range(1, N+1):
    for j in range(1, i+1):
        if j + T[j-1] - 1 <= i:
            DP[i] = max(DP[i], DP[j-1] + P[j-1])

result = max(DP)

print(result)

설명

문제 설명

이 문제는 백준이가 퇴사하기 전에 할 수 있는 상담의 최대 이익을 구하는 문제이다. 남은 N 일 동안 상담을 통해서 최대한 많은 수익을 얻고 싶어한다. 각 상담을 완료하는 데 걸리는 기간(Ti)과 상담을 했을 때 받을 수 있는 금액(Pi)로 이루어져 있다. 이 문제의 목표는 상담 일정을 잘 조정하여 백준이가 얻을 수 있는 금액을 최대로 하는 금액을 구하는 것이다.

문제 접근 방법

이 문제를 해결할려면 복잡한 문제를 여러 개의 부분 문제로 나누어 해결한 뒤 그 결과를 저장해두었다가 나중에 부분 문제를 합쳐서 복잡한 문제를 해결하는 방식인 "다이나믹 프로그래밍" 기법을 사용하여 해결한다.

알고리즘 설명

1. 입력 받기 : 먼저 N, T, P 를 입력 받는다. 각각은 상담 가능한 날짜 수, 각 상담을 완료하는 데 걸리는 기간, 상담을 완료했을 때 받을 수 있는 금액을 의미한다.
2. DP 배열을 초기화한다. N+1 크기의 DP 배열을 초기화한다. 이 배열의 각 요소는 해당 일까지 얻을 수 있는 최대 수익을 저장한다.
3. DP 를 이용하여 최대 수익을 계산한다.

• 외부 루프에서는 1일부터 시작하여 N 일까지 순회한다.
• 내부 루프에서는 현재 날짜(i) 와 상담을 시작할 수 있는 날짜(j)를 비교한다.
• 상담을 시작할 수 있는 날짜(j)는 상담 기간(T[j-1])을 고려하여 현재 날짜(i) 이전이어한다.
• 조건을 만족하는 경우, DP 배열을 업데이트합니다. 즉, DP[i] 는 현재 저장된 값과 DP[j-i] + P[j-i] 중 더 큰 값으로 업데이트한다.

4. 결과를 출력한다. 결과는 DP 배열에서 가장 큰 값을 찾으면 된다.

코드 설명

1. N, T, P를 입력받아 초기화
2. DP = [0] * (N+1)을 통해 DP 배열을 초기화한다. 이 배열은 각 일자까지 얻을 수 있는 최대 수익을 저장한다.
3. 이중 for 루프를 사용하여 모든 가능한 상담 조합을 해보는 것이다. 내부 루프에서 j + T[j-1] - 1 <= i 조건을 통해 상담을 완료할 수 있는지 확인을 하고 진행한다. 가능하다면, DP[i]를 현재 값과 DP[j-1] + P[j-1] 중 더 큰 값으로 업데이트한다. 4, 마지막으로 max(DP)를 통해 DP 배열에서 가장 큰 값을 찾아 출력한다. 이 값이 최대 수익이다.

정답 코드 및 설명

전체 코드

n, m = map(int, input().split())
a = list(map(int, input().split()))

# 누적 합 배열 계산
s = [0] * (n+1)
for i in range(1, n+1):
    s[i] = s[i-1] + a[i-1]

# 나머지에 대한 카운트 배열
remainder_count = [0] * m
for sum_value in s:
    remainder_count[sum_value % m] += 1

# 조건을 만족하는 구간의 개수 계산
result = 0
for count in remainder_count:
    if count > 1:
        result += count * (count - 1) // 2

print(result)

문제 설명

주어진 숫자 리스트에서 연속된 숫자들의 합이 특정 숫자 M 으로 나누어 떨어지는 구간(부분 리스트)의 개수를 찾는 것이다.

예를 들어 리스트가 [1,2,3,1,2] 이고 M = 3 일 때 이 리스트에서 합이 3으로 나누어 떨어지는 연속된 구간을 찾아야 한다.

• [1,2] 의 합이 3 M = 3 으로 나누어 떨어진다
• [2,1]
• [1,2,3]
• [3]
• [2,3,1]
• [3,1,2]
• [1,2,3,1,2]

총 7개 구간이 조건을 만족한다.

문제 접근 방법

1. 누적 합 계산 : 먼저 리스트의 각 위치까지의 합을 순서대로 계산한다.
2. 나머지 활용 : 누적 합의 각 값에 대해 M 으로 나눈 나머지를 계산한다. 같은 나머지를 가지는 누적 합의 값들 사이에는 그 차이가 M 의 배수라는 것을 의미하므로 이 구간의 합은 M 으로 나누어 떨어진다.
3. 구간 개수 계산 : 나머지가 같은 누적 합의 값들이 몇 번 나타났는 지 수를 센다. 나머지가 0 인 경우 합 자체가 M 으로 나누어 떨어지는 경우를 의미하므로, 이 경우도 포함된다.
4. 결과를 출력한다.

코드 설명

1. n 과 m 을 입력 받고 a 리스트 각 요소를 입력받는다.
2. 누적합 배열 계산

• n+1 크기의 리스트 s 를 생성하고 모든 요소를 0으로 초기화한다. s 는 누적합을 저장할 배열이다.
• for 루프 를 사용하여 리스트 a의 각 요소에 대해 누적 합을 계산하고, s 에 저장한다. s[i]는 a 리스트의 첫 번째 요소부터 i 번째 요소까지의 합을 나타낸다.

3. 나머지에 대한 카운트 배열

• 길이가 m 인 리스트 remainder_count 를 생성하고, 모든 요소를 0 으로 초기화 한다. 이 배열은 누적 합의 나머지 값을 카운트한다.
• 누적 합 배열 s를 순회하며 각 요소를 m 으로 나눈 나머지를 계산한다. 계산된 나머지를 인덱스로 사용하여 remainder_count 배열의 해당 요소를 1 증가시킨다.

4. 조건을 만족하는 구간의 개수를 계산한다

• result 결과를 저장할 변수 를 0으로 초기화한다.
• remainder_count 배열을 순회하며, 각 나머지 값이 나타난 횟수 count 에 대해 조건을 만족하는 구간의 개수를 계산한다. 구간의 개수 count 가 2 이상일 때, count * ( count - 1 ) /2 로 계산한다. 이는 해당 나머지를 가지는 누적 합의 값들 사이에서 2개를 선택하는 조합의 수를 의미한다.
• 각 나머지 값에 대해 계산된 구간의 개수를 result 에 더한다

5. 결과를 출력한다.

정답 코드 및 설명

전체 코드

# 문자열 입력
string_input = input().strip()

# 쿼리 수 입력
query_count = int(input())

# 누적 합 배열 초기화
cumulative_sums = [[0 for _ in range(26)] for _ in range(len(string_input))]

# 첫 문자에 대한 누적 합 설정
cumulative_sums[0][ord(string_input[0]) - ord('a')] = 1

# 나머지 문자에 대한 누적 합 계산
for index in range(1, len(string_input)):
    cumulative_sums[index][ord(string_input[index]) - ord('a')] = 1
    for char_index in range(26):
        cumulative_sums[index][char_index] += cumulative_sums[index - 1][char_index]

# 쿼리 처리
for _ in range(query_count):
    char, start, end = input().split()
    start, end = int(start), int(end)
    # 구간 내 출현 횟수 계산
    if start > 0:
        result = cumulative_sums[end][ord(char) - ord('a')] - cumulative_sums[start - 1][ord(char) - ord('a')]
    else:
        result = cumulative_sums[end][ord(char) - ord('a')]
    # 결과 출력
    print(result)

문제 설명

문자열에서 주어진 구간 내에 특정 문자가 몇 번 등장하였는 지 계산하는 문제이다. 문자열과 쿼리 수 긜고 각 쿼리에 대한 정보(특정 문자와 구간)가 주어진다.

접근법

누적 합 기법을 사용한다. 누적 합을 계산하여 각 알파벳에 대해 문자열의 시작부터 현재 위치까지 각 알파벳이 몇 번 나타났는지 저장한다. 이렇게 하면 각 쿼리를 빠르게 처리할 수 있다.

코드 설명

1. 문자열 'S' 와 쿼리 수 'Q' 를 입력받는다.
2. 각 알파벳에 대한 누적 합 배열 CumulativeSums를 초기화 한다.
3. 문자열 'S' 를 순회하며 각 문자에 대한 누적 합을 계산한다.
4. 쿼리를 순회하며 각 쿼리에 대해 계산한다.

• 주어진 구간 [start, end] 내에 특정 문자가 몇 번 나타나는지 CumulativeSums를 이용하여 계산

5. 각 쿼리마다 계산한 결과를 출력한다.

Python3으로 제출하니 50점을 맞았지만 pypy3로 제출하니 100점을 맞을 수 있었다.

정답 코드 및 설명

전체 코드

# 입력 받기
N, K = map(int, input().split()) # N은 전체 날짜의 수, K는 연속적인 날짜의 수
temperatures = list(map(int, input().split())) # 매일의 온도

# 슬라이딩 윈도우 초기화
current_sum = sum(temperatures[:K]) # 처음 K일 동안의 온도 합
max_sum = current_sum

# 슬라이딩 윈도우를 이용한 최대 온도 합 계산
for i in range(K, N):
    current_sum += temperatures[i] - temperatures[i-K]
    max_sum = max(max_sum, current_sum)

# 최대 온도 합 출력
print(max_sum)

문제 설명

위 수열 문제는 일정 기간 동안 매일 측정된 온도가 정수의 수열로 주어진다. 목표는 연속적인 며칠 동안의 온도의 합이 최대가 되는 값을 찾는 것이다. 즉, 주어진 수열에서 특정 길이 K 의 연속된 부분 수열의 합 중 최댓값을 찾아야 한다.

위 문제를 효율적으로 풀기 위한 방법 중 하나는 '슬라이딩 윈도우' 기법을 사용하는 것이다. 슬라이딩 윈도우 기법은 배열이나 리스트의 일정 범위의 데이터를 연속적으로 처리해야할 때 사용하는 알고리즘 기법이다. 이 기법의 핵심은 윈도우 라고 할 수 있는 고정된 크기의 범위를 가지고 이 범위를 배열이나 리스트를 따라 한 칸 씩 이동하면서 필요한 계산을 수행하는 것이다.

코드 설명

1. 먼저 k개의 요소로 구성된 윈도우 합을 계산한다. 이를 current_sum 으로 한다 이는 0~k 의 원소 합이다.

2. 윈도우를 한 칸 씩 오른쪽으로 이동하면서 새로 윈도우에 들어오 는 요소를 current_sum 에 더하고 윈도우에서 빠져나가는 요소를 current_sum 에서 뺴준다. 이렇게 하여 갱신된 current_sum 이 이전의 max_sum 보다 크면 max_sum 을 바꿔준다

3. 모든 위치에서 슬라이딩이 끝나면 계산된 최대 합 max_sum 을 출력한다.

정답 코드 및 설명

전체 코드

N, M = map(int, input().split())
arr = list(map(int, input().split()))

prefixSum = [0] * (N+1)
for i in range(1, N+1):
    prefixSum[i] = prefixSum[i-1] + arr[i-1]

for _ in range(M):
    i, j = map(int, input().split())
    print(prefixSum[j] - prefixSum[i-1])

문제 설명

구간 합 구하기 문제는 특정 구간의 합을 빠르게 계산하는 것이다. 이 문제를 효율적으로 해결하기 위해 사용하는 기법 누적 합을 사용하는 것이다

누적 합(Prefix Sum) 알고리즘

누적 합 알고리즘은 배열의 각 위치에 대해, 그 위치까지의 모든 원소들의 합을 미리 계산해 두는 방법이다. 이렇게 하면, 어떤 구간의 합을 구하고자 할때, 해당 구간의 끝 지점까지의 누적 합에서 시작 지점 이전까지의 누적합을 빼주기만 하면, 그 구간의 합을 매우 빠르게 계산할 수 있다.

코드 설명

1. 입력으로 주어진 N개의 수에 대해서 누적합을 먼저 계산한다. prefixsum 배열을 사용하는 데 prefixSum[i] 는 주어진 배열의 첫 번째 원소부터 i 번째 원소까지의 합을 저장한다.

2. prefixSum[0] 을 0으로 먼저 초기화한다. 이는 구간의 시작 지점이 1번째 원소일 경우를 처리를 위한 초기화이다.

3. prefixSum 배열을 채울 때 각 i 에 대하여 prefixSum[i] = prefixSum[i-1] + arr[i-1] 공식을 사용한다. 이 공식은 이전까지의 누적 합에 현재 원소를 더해 다음 누적 합을 계산한다.

4. 구간 합을 구하려 할 때는, 주어진 구간 [i,j] 에 대하여 prefixSum[j] - prefixSum[i-1] 을 계산한다. 이는 i 번째 원소부터 j 번째 원소까지의 합과 같다.

시간 초과 문제

입력 방식을 sys 를 이용해 입력 받는 것으로 변경한 코드이다.

import sys

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

prefixSum = [0] * (N+1)
for i in range(1, N+1):
    prefixSum[i] = prefixSum[i-1] + arr[i-1]

for _ in range(M):
    i, j = map(int, sys.stdin.readline().split())
    print(prefixSum[j] - prefixSum[i-1])

위 코드로 문제를 풀 수 있다.

정답 코드 및 설명

전체 코드

N, K = map(int, input().split())  # 물품의 수 N, 가방에 넣을 수 있는 무게 K 입력 받기
Things = []  # 물품의 무게와 가치를 저장할 배열

# 입력 받아서 Things에 삽입
for i in range(N):
    w, v = map(int, input().split())  # 물품의 무게 w와 가치 v 입력 받기
    Things.append((w, v))

# 해를 담을 Pack 배열 초기화, 최적해는 Pack[N][K]
Pack = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

# 동적 프로그래밍으로 Pack 배열 채우기
for i in range(1, N + 1):
    for k in range(1, K + 1):
        if Things[i-1][0] > k:  # 물건 i의 무게가 임시 배낭 용량을 초과하면
            Pack[i][k] = Pack[i-1][k]
        else:  # 물건 i를 배낭에 담지 않을 경우와 담을 경우 각각을 고려
            Pack[i][k] = max(Pack[i-1][k], Pack[i-1][k - Things[i-1][0]] + Things[i-1][1])

print(Pack[N][K])  # 모든 물건의 가치 합(최적해) 출력

코드 설명

위 문제는 물건, 물건의 무게, 물건의 가치, 들 수있는 최대 용량, 총 4개의 요소가 있다.

이를 생각했을때, 최대로 들 수 있는 용량을 고려하는 게 아닌 0 부터 최대로 들 수 있는 용량을 고려하되 물건 1 부터 i 까지 고려하는 방법을 사용한다.

Pack[i,k] 가 의미하는 것은 물건 1부터 i까지 고려하고, 최대 용량이 k 일때 최대 가치를 의미한다.

문제의 정답은 Pack[N][K] 가 되는 것이다.

먼저 최대 들 수 있는 용량이 0 이라고 했을 때 Pack[i,0] = 0 으로 초기화 해준다. 넣을 수 있는 물건이 0 이므로 Pack[0,w] 도 0으로 채워 준다

다음으로 for 문을 생성하는 데 이중 포문을 사용한다. 제일 바깥쪽 for 문은 물건 1부터 i 까지 순회하고 그 다음 for 문은 최대 들 수 있는 용량이 1부터 K 까지 순회한다.

후에 if 문을 통해 지금 선택된 물건 i 의 무게가 현재 넣을 수 있는 무게 k 를 초과한다면 Pack[i,w] 는 이전 값이 유지된다. Pack[i-1,w] 현재 선택된 물건 i 의 값이 넣을 수 있는 무게라면 Pack[i,w] 는 물건 i를 가방에 넣지 않을 경우와 넣을 경우를 비교해서 더 가치있는 것을 선택하면 된다.

Pack[i,w] = Pack[i][k] = max(Pack[i-1][k], Pack[i-1][k - Things[i-1][0]] + Things[i-1][1])

이중 for 문을 전부 순회했다면 맨 끝에 있는 값이 정답이 된다.

정답 코드 및 설명

정답 전체 코드

A_string = input().rstrip()
B_string = input().rstrip()

LCS = [[0] * (len(B_string) + 1) for _ in range(len(A_string) + 1)]

for i in range(1, len(A_string) + 1):
    for j in range(1, len(B_string) + 1):
        if A_string[i-1] == B_string[j-1]:
            LCS[i][j] = LCS[i-1][j-1] + 1
        else:
            LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

print(LCS[-1][-1])

문제 설명

위 문제는 LCS, Longest Common Subsequence 최장 공통 부분 수열을 찾는 문제이다.

두 문자열, 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예시로써

ACAYKP 와 CAPCAK 의 LCS 는 ACAK 가 된다.

코드 설명

1. 먼저, 문자열 두 개를 A, B 로써 입력 받는다.

LCS 배열을 하나 만들어 초기화한다. 이 배열의 크기는 A와 B 문자열 길이에 각각 한 칸 더 늘어난 크기로 설정한다.

그 이유는 LCS 를 찾기 위해서 현재 A문자열에서 선택된 문자와 B문자열에서 선택된 문자를 비교할 텐데 부분 수열은 연속된 값이 아니고 이전 값이 유지되기 때문에 이전 값과 비교하기 위해서 한 칸을 늘려준다.

LCS 에 대한 자세한 설명은 아래 링크를 참고했다. 그림으로 자세히 설명이 되어있어 도움이 되었다.

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

2. 이후 A문자열 과 B문자열의 각 문자 하나하나 씩 비교하는 이중 for 문을 통해 검사한다.

두 문자가 다르면 LCS[i-1][j] 와 LCS[i][j-1] 둘 중 큰 값을 선택한다.

두 문자가 같다면 LCS[i][j] = LCS[i-1][j-1] + 1 이 된다.

3. 최장 공통 부분 수열의 크기를 출력한다.

최장 공통 부분 수열의 크기는 LCS 배열에서 가장 큰 값이 된다.

정답 코드 및 설명

전체 코드

n = int(input())
connections = []
for _ in range(n):
    a,b = map(int, input().split())
    connections.append((a,b))

# a 전봇대 기준으로 정렬
connections.sort()

# b 전봇대 위치만 추출
b_positions = [b for a,b in connections]

dp = [1] * n
for i in range(n):
    for j in range(i):
        if b_positions[i] > b_positions[j]:
            dp[i] = max(dp[i], dp[j] +1)

print(n - max(dp))

풀이 설명

전깃줄이 교차 하지 않을려면 어떻게 해야할까?

한 전봇대에서 연결 순서가 다른 전봇대에서도 증가하는 순서로 연결되어야 한다.

즉, 한 전봇대에 대해서 연결 위치를 기준으로 정렬한 후, 다른 전봇대에 대해서 연결 위치의 최장 증가 부분 수열(LIS) 를 찾는다. 찾은 LIS 의 길이는 최대로 교차하지 않는 전깃줄의 수가 된다.

전체 전깃줄에서 찾은 LIS 길이( = 최대로 교차하지 않는 전깃줄 수) 를 빼준다면 제거해야할 전깃줄 수의 최소가 나오게 된다.

코드 설명

1. 전깃줄의 갯수와 각 전깃줄의 A,B 전봇대에 연결된 위치 정보를 입력받는다.
2. 입력받은 연결 정도를 A 전봇대 위치 기준으로 오름차순으로 정렬한다.
3. B 전봇대의 위치 정보만 빼서 배열을 생성한다.
4. 생성된 배열에 대해 LIS 를 찾는다.
5. 전체 전깃줄 개수 에서 LIS 길이를 빼서, 교차하지 않게 하기 위해 제거해야할 전깃줄의 최소 개수를 계산하고 출력한다.

정답 코드 및 설명

전체 코드

N = int(input())
A = list(map(int, input().split()))

increase = [1 for _ in range(N)]
decrease = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            increase[i] = max(increase[i], increase[j]+1)

for i in range(N-1,-1,-1):
    for j in range(N-1, i ,-1):
        if A[j] < A[i]:
            decrease[i] = max(decrease[i], decrease[j] + 1)


max_length = 0
for i in range(N):
    max_length = max(max_length, increase[i] + decrease[i] - 1)

print(max_length)

설명

가장 긴 바이토닉 부분 수열을 찾기 위해서는 두 단계의 DP 배열을 계산해야한다. 하나는 왼쪽에서 오른쪽으로 진행하며 각 위치에서 가장 긴 증가하는 부분 수열의 길이를 찾는 것이고, 다른 하나는 오른쪽에서 왼쪽으로 진행하며 각 위치에서 가장 긴 감소하는 부분 수열의 길이를 찾는 것이다.

이후, 각 위치에서 가장 긴 증가하는 부분 수열의 길이와 가장 긴 감소하는 부분 수열의 길이를 합친 값에서 1을 빼면(해당 위치 값이 두 수열에서 중복으로 계산되기에), 해당 위치를 기준으로 하는 가장 긴 바이토닉 부분 수열의 길이를 얻을 수 있다.

알고리즘 의사 코드

1. N 과 수열 A 를 입력받는다.
2. 배열 increase 와 decrease 를 길이 N 으로 초기화한다. 이 배열들은 각각 각 위치에서 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열의 길이를 저장할 것이다.
3. 왼쪽에서 오른쪽으로 진행하며 increase 배열을 채운다.

• 각 i 에 대해서 j < i 인 모든 j 에 대해서 A[j] < A[i] 이면, increase[i] = max(increase[i] , increase[j] + 1) 로 업데이트 한다.

4. 오른쪽에서 왼쪽으로 진행하며 decrease 배열을 채운다

• 각 i 에 대해 j > i 인 모든 j 에 대해서 A[j] < A[i] 이면 decrease[i] = max(decrease[i] , decrease[j] + 1) 로 업데이트 한다.

5. 모든 위치 i 에 대해 increase[i] + decrease[i] - 1 을 계산하고, 이 값들 중 최댓값을 찾는다. 이 최댓값이 가장 긴 바이토닉 부분 수열의 길이이다.

정답 코드 및 설명

N = int(input())
A = list(map(int, input().split()))

# DP 배열 초기화
dp = [1] * N  # 각 위치에서의 최대 증가 부분 수열 길이

# LIS 계산
for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j] + 1)

# 가장 긴 증가하는 부분 수열의 길이 출력
print(max(dp))

문제 이해

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence, LIS) 문제는 주어진 수열에서 특정 숫자들을 순서대로 선택했을 때, 이들이 증가하는 순서를 유지하면서 구성되는 가장 긴 부분의 부분 수열을 찾는 문제이다. 부분 수열은 주어진 수열의 원소들 중 일부를 순서대로 선택하여 구성되며, 선택된 원소들 사이에 다른 원소들이 있을 수 있다.

위 문제 해결 알고리즘 의사 코드

1. 입력 : 수열의 크기 N 과 수열 A 를 입력 받는다.

2. DP 배열 초기화 : 길이 N 의 배열 dp 를 생성하고 모든 값을 1로 초기화한다. dp[i] 가 의미하는 것은 위치 i 에서 끝나는 가장 긴 증가하는 부분 수열의 길이를 나타낸다.

3. LIS 계산하기

• 모든 위치 i에 대해 0 부터 i-1 까지의 위치 j 를 검사한다.
• 만약 A[i] 가 A[j] 보다 크다면, dp[i] 는 dp[j] +1 과 dp[i] 중 더 큰 값으로 변경한다
• 위 과정은 A[i] 가 A[j] 보다 크고, j 에서 끝나는 부분 수열 뒤에 A[i] 를 추가하여 더 긴 부분 수열을 만들 수 있음을 의미한다.

4. 결과 출력 : dp 배열 내에서 가장 큰 값을 출력한다.

정답 코드 및 설명

전체 코드

def min_operations(n):
    dp = [0] * (n + 1)  # dp 배열 초기화

    for i in range(2, n + 1):
        # 기본 연산: 1 빼기
        dp[i] = dp[i - 1] + 1

        # 2로 나누기 가능 시 최솟값 갱신
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)

        # 3으로 나누기 가능 시 최솟값 갱신
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)

    return dp[n]

print(min_operations(int(input()))) 

각 정수에 대하여 1로 만드는 데 필요한 최소 연산 횟수를 저장하는 방식으로 문제를 푼다.

1. 정수 N 을 1로 만들기 위한 최소 연산 횟수를 저장할 배열 dp 를 생성하고 dp[i] 는 정수 i를 1로 만들기 위한 최소 연산 횟수이다.

2. dp[1] 은 0으로 초기화 한다

3. 모든 정수 i 에 대해서 다음 3가지 연산 중 하나를 적용할 수 있다.

   • 만약 i 가 3으로 나누어 떨어진다면, dp[i/3] + 1 을 계산한다
   • 만약 i 가 2으로 나누어 떨어진다면, dp[i/2]+ 1 을 계산한다
   • dp[i-1] + 1 을 계산한다

4. 위 3 가지 연산으로 계산된 값 중 최소값을 dp[i] 에 저장한다

정답 코드 및 설명

전체 코드

import sys

# 입력을 빠르게 받기 위한 설정
input = sys.stdin.readline

n = int(input())
stairs = [int(input().strip()) for _ in range(n)]

# dp 배열 초기화
dp = [0] * n
dp[0] = stairs[0]
if n > 1:
    dp[1] = stairs[0] + stairs[1]
for i in range(2, n):
    dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])

print(dp[n-1])

코드 설명

1. 계단 점수 입력 받기

import sys
input = sys.stdin.readline

n = int(input())
stairs = [int(input().strip()) for _ in range(n)]

입력을 빠르게 받기 위해 sys 를 사용했고, staris 를 입력 받는 부분을 간략하게 list comprehension 을 사용했다.

2. dp 배열 초기화

   dp = [0] * n
   dp[0] = stairs[0]
   if n > 1:
    dp[1] = stairs[0] + stairs[1]

   동적 프로그래밍을 위해서 dp 배열을 생성하고 0번째를 제일 처음에 있는 계단으로 하고, dp[1] 은 n 이 1보다 클 때 첫번째 계단 점수와 두번째 계단 점수를 합한 값으로 설정한다.

3. 점화식을 이용하여 계산

   for i in range(2, n):
    dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])

   문제에서 계단을 오를 때 두 가지 주요 규칙을 생각해야한다.

• 한 계단을 오르는 경우

• 두 계단을 오르는 경우

  이에 더해서 연속 세 계단을 밟지 않는 규칙을 준수해야한. 따라서 마지막으로 밟을 계단을 기준으로 이전 계단을 밟았는지, 아니면 두 계단 전에 밟았는 지에 따라 경우를 나누어 점화식을 결정한다.

• 한 계단을 오르는 경우 dp[i-2] + stairs[i] i-2 번째 계단에서 직접 i 번째 계단으로 뛰어넘어 오르는 상황이다. 즉, i-1 번째 계단은 건너 뛰고 i 번째 계단으로 직접 오르는 것이다.

• 두 계단을 오르는 경우 dp[i-3] + stairs[i-1] + stairs[i] i-3 번째 계단에서 i-1 계단을 거쳐 i 번째 계단을 오르는 상황을 나타낸다. 이는 연속해서 세 계단을 밟지 않고 마지막 두 계단을 연속해서 밟아 오르는 경우이다. 이 경우 i-1 번째와 i 번째 계단의 점수를 모두 더한다.

점화식 부분이 이해 되지 않는 다면 참고 링크에 설명이 잘되어있다.

정답 코드 및 설명

전체 코드

n = int(input())
triangle = []

# 삼각형 데이터 입력받기
for _ in range(n):
    triangle.append(list(map(int, input().split())))

# 동적 프로그래밍을 위한 2차원 DP 테이블 초기화
dp = [[0] * n for _ in range(n)]
dp[0][0] = triangle[0][0]

# 삼각형의 각 층을 순회하며, 각 위치에서의 최대 합 계산
for i in range(1, n):
    for j in range(i + 1):
        # 왼쪽 대각선 위에서 내려오는 경우
        if j > 0:
            left_up = dp[i-1][j-1]
        else:
            left_up = 0

        # 바로 위에서 내려오는 경우 (오른쪽 대각선을 고려하지 않음, 삼각형의 형태상 바로 위에서 내려올 수 없음)
        if j < i:
            up = dp[i-1][j]
        else:
            up = 0

        # 현재 위치에서의 최대 합 업데이트
        dp[i][j] = max(left_up, up) + triangle[i][j]

# 마지막 층에서의 최대값 찾기
result = max(dp[n-1])

print(result)

코드 설명

1. 삼각형 데이터 입력 받기

   triangle = []
   for _ in range(n):
    triangle.append(list(map(int, input().split())))

   크기가 n 으로 입력 받은 값을 이용하여 삼각형을 입력 받는다.

2. 동적 프로그래밍을 위해 dp 테이블을 만들어준다

   # 동적 프로그래밍을 위한 2차원 DP 테이블 초기화
   dp = [[0] * n for _ in range(n)]
   dp[0][0] = triangle[0][0]
   

dp 테이블을 0으로 초기화 하고 처음 0,0 은 삼각형의 맨 위 꼭짓점 부분으로 비교할 필요가 없으니 설정해준다.

3. 삼각형의 각 층을 순회하면서, 각 위치에서의 최대 합을 계산한다. 

for i in range(1, n): for j in range(i + 1):

i 는 1부터 n-1 까지이다 이는 삼각형 2번째 줄부터 순회한다는 뜻이고 
j 는 0부터 i+1 까지인데 이는 i번째 줄의 항목을 순회한다는 뜻이다.

    # 왼쪽 대각선 위에서 내려오는 경우
    if j > 0:
        left_up = dp[i-1][j-1]
    else:
        left_up = 0

    # 바로 위에서 내려오는 경우 (오른쪽 대각선을 고려하지 않음, 삼각형의 형태상 바로 위에서 내려올 수 없음)
    if j < i:
        up = dp[i-1][j]
    else:
        up = 0

    # 현재 위치에서의 최대 합 업데이트
    dp[i][j] = max(left_up, up) + triangle[i][j]

아래로 내려갈 경우 2가지 경우가 있다. 

- 왼쪽 대각선 위에서 내려올 경우 
이 경우는 현재 숫자의 위치가 그 층의 첫번째면 내려올수 없기에, j > 0 이라는 조건을 먼저 필터링해준다. dp[i-1][j-1] 에서 현재 숫자를 더한 값을 고려한다
- 바로 위에서 내려올 경우 
이 경우는 현재 숫자의 위치가 그 층의 마지막 숫자가 아닐때만 가능하다. 즉, j < i 일 때이다. 이 경우는 dp[i-1][j] 에서 현재 숫자를 더한 값을 고려한다.

그 후 현재 위치에서 구한 최대 합을 업데이트 한다. dp[i][j] 에 현재 위치 값 triangle[i][j] 와 이전에 구한 왼쪽 위, 바로 위 를 비교해서 높은 것을 더해준다. 

4. 마지막 층에서 최대값 찾기 

마지막 층에서의 최대값 찾기

result = max(dp[n-1])

print(result)

결과적으로 마지막 까지 간 값 중에서 최대값을 찾으면 되기 때문에, max(dp[n-1]) 해서 정답을 찾을 수 있다.

정답 코드 및 설명

전체 코드

def find_min_cost(cost, N):
    dp = [[0 for _ in range(3)] for _ in range(N)]

    for color in range(3):
        dp[0][color] = cost[0][color]

    for i in range(1, N):
        dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])
        dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])
        dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1])

    return min(dp[N-1][0], dp[N-1][1], dp[N-1][2])

# 집의 수 입력 받기 
N = int(input())
# 각 집을 빨강, 초록, 파랑으로 칠하는 비용 입력 받기
cost = []
for _ in range(N):
    cost.append(list(map(int, input().split())))

# 최소 비용 계산 및 출력
min_cost = find_min_cost(cost, N)
print(min_cost)

코드 설명

1. 사용자로부터 집의 수 N을 입력받는다.
2. 사용자로부터 각 집을 빨강, 초록, 파랑으로 칠하는 비용을 입력받는다. 각 비용은 공백으로 구분되며, N번 반복하여 입력받는다.
3. 입력받은 비용을 바탕으로 모든 집을 칠하는 최소 비용을 계산한다.
4. 계산된 최소 비용을 출력한다.

주요 함수 설명

def find_min_cost(cost, N):
    dp = [[0 for _ in range(3)] for _ in range(N)]

    for color in range(3):
        dp[0][color] = cost[0][color]

    for i in range(1, N):
        dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])
        dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])
        dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1])

    return min(dp[N-1][0], dp[N-1][1], dp[N-1][2])

위 문제를 해결하기 위해 작성한 코드로 문제에 주어진 집들을 RGB 색상으로 칠할 때, 각 색상별로 비용이 주어지고 인접한 집들이 같은 색으로 칠해지지 않도록 하면서 전체 비용을 최소화하는 문제에 적용하는 함수이다.

cost 각 집을 R G B 로 칠해하는 데 드는 비용을 저장한 2차원 리스트이다. cost[i][0], cost[i][1], cost[i][2]는 각각 i번째 집을 R, G, B로 칠하는 비용이다. N은 집의 총 수를 나타내는 정수이다.

함수 동작 과정

1. DP 테이블 초기화: dp 테이블은 각 집을 R, G, B로 칠할 때까지의 최소 비용을 저장한다. dp[i][color]는 0번째부터 i번째 집까지 고려했을 때, 마지막 집(i번째 집)을 color 색으로 칠했을 때의 최소 비용이다.

2. 첫 번째 집 칠하기: 첫 번째 집을 R, G, B로 칠하는 비용을 dp[0][color]에 저장한다. 이는 초기 조건을 설정하는 단계이다.

3. 점화식을 통한 최소 비용 계산:

각 집 i에 대해, dp[i][color]를 계산한다. 이는 "i번째 집을 특정 색으로 칠했을 때의 비용 + i-1번째 집을 다른 두 색 중 하나로 칠했을 때의 최소 비용"으로 정의된다. 예를 들어, dp[i][0] (i번째 집을 R로 칠하는 경우)의 비용은 cost[i][0] + min(dp[i-1][1], dp[i-1][2])로 계산된다. 여기서 cost[i][0]은 i번째 집을 R로 칠하는 비용이고, min(dp[i-1][1], dp[i-1][2])는 이전 집(i-1번째 집)을 G나 B로 칠했을 때의 최소 비용이다.

4. 최소 비용의 결정:

모든 집을 칠했을 때의 최소 비용은 min(dp[N-1][0], dp[N-1][1], dp[N-1][2])로 결정된다. 이는 마지막 집(N-1번째 집, 인덱스는 0부터 시작하므로)을 R, G, B 중 어떤 색으로 칠했을 때의 최소 비용 중 가장 작은 값을 의미한다.