TIL 코딩공장

백준 파이썬 공부 2025.10.01
14891번 톱니바퀴 (골드 5)

1. 문제
총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 
또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 
톱니바퀴에는 번호가 매겨져 있는데, 
가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 
톱니바퀴의 회전은 한 칸을 기준으로 한다. 
회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 
톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 
옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 
톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, 
B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 

예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 
여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 
2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 
1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 
따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 
2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 
2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 
4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 
따라서, 아래와 같은 상태가 된다.

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 
최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 
셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 
상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. 
N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 
다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 
각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 
방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

3. 출력
총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 
점수란 다음과 같이 계산한다.

- 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
- 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
- 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
- 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

4. 문제 풀이
구현 및 시뮬레이션 문제이다.
파이썬의 경우, 해당 문제의 톱니바퀴 회전을 deque의 rotate 함수를 사용하면 쉽게 풀이가 가능하다.

<주의할 점>
- 회전 후 맞닿은 부분이 다를 경우에만, 반대방향으로 회전 (같은 경우 회전 안함)
- 점수의 계산의 모든 회전이 끝난 후에 한번만 시행

>>코드

'''
14891번 톱니바퀴
입력 : cog (톱니바퀴의 상태),
k (회전 수), roll (회전 톱니바퀴와 방향)
출력 : 네 톱니바퀴의 점수 합
'''
import sys
from collections import deque

input = sys.stdin.readline

cog = [deque(map(int, list(input().strip()))) for _ in range(4)]
k = int(input())
roll = [list(map(int, input().split())) for _ in range(k)]
    
for c, d in roll:
    c -= 1
    # 톱니바퀴 회전 방향 저장
    direction = [0] * 4
    direction[c] = d
    
    # 앞쪽 톱니바퀴 회전 확인
    for i in range(c+1, 4):
        if cog[i-1][2] != cog[i][6]:
            direction[i] = -direction[i-1]
        else:
            break
    # 뒤쪽 톱니바퀴 회전 확인
    for i in range(c-1, -1, -1):
        if cog[i+1][6] != cog[i][2]:
            direction[i] = -direction[i+1]
        else:
            break
    # 회전 적용
    for i in range(4):
        if direction[i]:
            cog[i].rotate(direction[i])

# 점수 계산
score = 0    
for i in range(4):
    if cog[i][0]:
        score += 2 ** i

print(score)

5. 문제 링크
https://www.acmicpc.net/problem/14891

백준 파이썬 공부 2025.09.30
14890번 경사로 (골드 3)

1. 문제
크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 
길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.

다음과 같은 N=6인 경우 지도를 살펴보자.

이때, 길은 총 2N개가 있으며, 아래와 같다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다.
또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 
경사로는 높이가 항상 1이며, 길이는 L이다. 
또, 개수는 매우 많아 부족할 일이 없다. 
경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

- 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
- 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
- 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

- 경사로를 놓은 곳에 또 경사로를 놓는 경우
- 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
- 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
- 경사로를 놓다가 범위를 벗어나는 경우

L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

경사로를 놓을 수 없는 경우는 아래와 같다.

위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 
1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 
3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.

가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 파란색으로, 
지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 
둘째 줄부터 N개의 줄에 지도가 주어진다. 
각 칸의 높이는 10보다 작거나 같은 자연수이다.

3. 출력
첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

4. 문제 풀이
고려해야할 조건이 굉장히 많은 문제이다

<조건>
- 높이 차이가 1 초과 → 실패 >> return False
- 같은 높이 → 계속 진행 >> continue
- 오르막 (앞칸 높이 < 뒷칸 높이)
→ 뒤로 l칸 연속 확인 필요 >> i-l ~ i-1 까지 같은 높이인지 검사
- 내리막 (앞칸 높이 > 뒷칸 높이) 
→ 앞으로 l칸 연속 확인 필요. >> i ~ i+l-1까지 같은 높이인지 검사
- 경사로는 겹칠 수 없음 >> used[] 리스트로 경사로 점거 확인

>>>코드

'''
14890번 경사로
입력 : n (지도의 가로세로 길이), l (경사로의 길이)
MAP (지도의 상황)
출력 : 가능한 길의 개수

함수
1. check(line) 해당 리스트의 road 검사
input : line (길 = 리스트)
output : True/False (길이 가능한지 반환)
'''
import sys
input = sys.stdin.readline

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

def check(line):
    # 경사도 설치 검사 리스트 used
    used = [0] * n
    for i in range(1, n):
        # 평지
        if line[i] == line[i-1]:
            continue
        # 경사도 1 초과
        elif abs(line[i] - line[i-1]) > 1:
            return False
        # 경사도 1 오르막
        elif line[i] > line[i-1]:
            for j in range(l):
                if i-j-1 < 0 or line[i-j-1] != line[i-1] or used[i-j-1]:
                    return False
                used[i-j-1] = 1
        # 경사도 1 내리막
        else:
            for j in range(l):
                if i+j >= n or line[i+j] != line[i] or used[i+j]:
                    return False
                used[i+j] = 1
    return True

road_cnt = 0
# 행 검사
for i in range(n):
    if check(MAP[i]):
        road_cnt += 1
# 열 검사
for j in range(n):
    col = [MAP[i][j] for i in range(n)]
    if check(col):
        road_cnt += 1

print(road_cnt)

5. 문제 링크
https://www.acmicpc.net/problem/14890

백준 파이썬 공부 2025.09.29
14499번 주사위 굴리기 (골드 4)

1. 문제
크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 
이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 
지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 

  2
4 1 3
  5
  6

주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 
놓여져 있는 곳의 좌표는 (x, y) 이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다.

지도의 각 칸에는 정수가 하나씩 쓰여져 있다. 
주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 
0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여 있는 수는 0이 된다.

주사위를 놓은 곳의 좌표와 이동시키는 명령이 주어졌을 때, 
주사위가 이동했을 때 마다 상단에 쓰여 있는 값을 구하는 프로그램을 작성하시오.

주사위는 지도의 바깥으로 이동시킬 수 없다. 
만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 하며, 출력도 하면 안 된다.

2. 입력
첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 
주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 
그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다.

둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 
주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 
지도의 각 칸에 쓰여 있는 수는 10 미만의 자연수 또는 0이다.

마지막 줄에는 이동하는 명령이 순서대로 주어진다. 
동쪽은 1, 서쪽은 2, 북쪽은 3, 남쪽은 4로 주어진다.

3. 출력
이동할 때마다 주사위의 윗 면에 쓰여 있는 수를 출력한다. 
만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 하며, 출력도 하면 안 된다.

4. 문제 풀이
구현 시뮬레이션 문제라고 볼 수 있다.
6면 주사위의 상태를 어떻게 저장하고 업데이트 할 것인지,
이동을 어떻게 구현할 것인지가 주요 포인트이다.

나는 리스트 dice = [윗면, 아랫면, 동, 서, 북, 남] 로 주사위의 상태를 저장하고,
이동에 따라 dice를 업데이트 하고, 원소들을 교환했다.

>>>코드

'''
14499번 주사위 굴리기
입력 : n, m (지도의 가로 세로), x, y (주사위 좌표), k (명령의 개수) 
MAP 지도의 상태, move 이동 명령
출력 : 주사위 윗면의 수

함수
1. roll (m) 이동방향에 따른 주사위 상태 업데이트
input : m 이동방향 (0 : 동, 1 : 서, 2 : 북, 3 : 남)
output : 없음 (주사위 dice 리스트 업데이트)

'''
import sys
input = sys.stdin.readline

n, m, x, y, k = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(n)]
move = list(map(int, input().split()))

# 순서대로 동, 서, 북, 남
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

# 주사위 초기 값 (윗면, 아랫면, 동, 서, 북, 남)
dice = [0] * 6

def roll(d):
    if d == 1:  # 동
        dice[0], dice[1], dice[2], dice[3] = dice[3], dice[2], dice[0], dice[1]
    elif d == 2:  # 서
        dice[0], dice[1], dice[2], dice[3] = dice[2], dice[3], dice[1], dice[0]
    elif d == 3:  # 북
        dice[0], dice[1], dice[4], dice[5] = dice[5], dice[4], dice[0], dice[1]
    elif d == 4:  # 남
        dice[0], dice[1], dice[4], dice[5] = dice[4], dice[5], dice[1], dice[0]

for d in move:
    nx = x + dx[d-1]
    ny = y + dy[d-1]
    # 주사위 이동 범위 검사
    if not (0 <= nx < n and 0 <= ny < m):
        continue
    else:
        x, y = nx, ny
    # 주사위 굴림 및 상태 업데이트
    roll(d)
    
    # 주사위와 지도 상호작용
    if MAP[x][y] == 0:
        MAP[x][y] = dice[1]
    else:
        dice[1] = MAP[x][y]
        MAP[x][y] = 0
    # 출력
    print(dice[0])

    

5. 문제 링크
https://www.acmicpc.net/problem/14499

백준 파이썬 공부 2025.09.28
14502번 연구소 (골드 4)

1. 문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 
다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 
직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 
연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 
새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 
아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 
위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 
0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 
2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

3. 출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

4. 문제 풀이
좋은... 문제다.
deque, BFS (너비우선탐색), DFS (깊이우선탐색), 백트래킹을 모두 사용해야되는 문제다.

1) wall () : 벽을 세우는 경우의 수
벽을 세우는 경우의 수를 확인하는 것은 백트래킹을 이용해서, 각각의 경우의 수를 모두 확인해야한다.
법칙이 없기때문에 중복없이 모두 확인해야한다. (브루트 포스)
당연하게도 백트래킹을 이용하면, DFS를 사용해야한다.

2) BFS() 바이러스 퍼짐
벽을 세운 경우에 대해, 바이러스 퍼짐을 확인해야되므로, 해당 MAP을 깊은 복사를 하여 확인해야된다.
(왜냐면, 바이러스 퍼짐을 확인 후에도 해당 원래 바이러스 위치를 알고 있어야 하므로 복사하여 사용)
바이러스가 퍼지는 것은 deque를 이용해서 BFS를 실행시켜, 바이러스가 퍼진 상태를 확인해야한다.

>>>코드

'''
14502번 연구소
입력 : n, m (지도의 가로 세로),  지도의 모양
출력 : 안전 영역 넓이의 최대값

함수
1. BFS() 바이러스 퍼짐 및 넓이 반환 (너비우선탐색)
input : wallmap (벽을 세운 맵 - 깊은 복사)
output : safty (안전구역 넓이)

2. wall() 벽 세우는 경우의 수 (백트래킹 및 깊이우선탐색)
input : depth (벽의 개수)
output : 없음
'''
from collections import deque
import copy

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

virus = []
for i in range(n):
    for j in range(m):
        if MAP[i][j] == 2:
            virus.append([i, j])
max_safty = 0

def BFS(wallmap):
    q = deque(virus)
    dr = [1, 0, -1, 0]
    dc = [0, 1, 0, -1]
    
    while q:
        r, c = q.popleft()    
    
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            
            if 0 <= nr < n and 0 <= nc < m:
                if wallmap[nr][nc] == 0:
                    wallmap[nr][nc] = 2
                    q.append((nr, nc))
                    
    safty = 0
    for i in range(n):
        safty += wallmap[i].count(0)
    
    return safty

def wall(depth):
    global max_safty
    if depth == 3:
        wallmap = copy.deepcopy(MAP)
        max_safty = max(max_safty, BFS(wallmap))
        return
    
    for i in range(n):
        for j in range(m):
            if MAP[i][j] == 0:
                MAP[i][j] = 1
                wall(depth+1)
                MAP[i][j] = 0

wall(0)
print(max_safty)

5. 문제 링크
https://www.acmicpc.net/problem/14502

백준 파이썬 공부 2025.09.27
14501번 퇴사 (실버 3)

1. 문제
상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 
비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 
5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 
예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 
2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 
이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 
1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

3. 출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

4. 문제 풀이
이전 값을 다음 값을 구하는데 사용하는 다이나믹 프로그래밍이 필요한 문제이다.

>>>틀렸습니다.

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

def max_profit():
    profit = [0] * (n+1)
    for day in range(n):
        d = day + councel[day][0] 
        if d <= n:
            expection = profit[day] + councel[day][1]
            profit[d] = max(expection, profit[d])
    return max(profit)

print(max_profit())

코드는 맞는 줄 알았는데, 현재 코드에서는 이익이 다음날까지 이어지지 않아 문제에 오류가 생겼다.
굳이 상담이 끝나는 날 있는 상담을 무조건 받아서 실행하는 것이 아니라,
쉬었다가 다음날 있는 더 비싼 상담을 받아도 되기 때문에,
오늘의 최대 이익이 다음날에도 이어지도록 계속해서 갱신해줘야 한다.
(비유하자면 이어달리기가 아니라 인터벌 달리기 느낌...?)

>>>정답 코드

'''
14501번 퇴사
입력 : n(퇴사일과 상담의 개수), T, P (상담 소요 시간과 금액)
출력 : 얻을 수 있는 최대 이익

함수
1. max_profit() 최대 이익 계산
input : n
output : max(profit) 최대 이익
'''

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

def max_profit():
    profit = [0] * (n+1)
    for day in range(n):
        profit[day + 1] = max(profit[day], profit[day + 1])
        d = day + councel[day][0] 
        if d <= n:
            expection = profit[day] + councel[day][1]
            profit[d] = max(expection, profit[d])
    return max(profit)

print(max_profit())

5. 문제 링크
https://www.acmicpc.net/problem/14501

백준 파이썬 공부 2025.09.26
14503번 로봇 청소기 (골드 5)

1. 문제
로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 N x M 크기의 직사각형으로 나타낼 수 있으며, 
1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 
청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 
가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다. 
즉, 좌표 (r, c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 
처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

1) 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.

2) 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
- 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
- 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

3) 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
- 반시계 방향으로 90도 회전한다.
- 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
- 1번으로 돌아간다.

2. 입력
첫째 줄에 방의 크기 N과 M이 입력된다. (3 <= N, M <= 50) 
둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r, c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. 
d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N x M개의 값이 한 줄에 M개씩 입력된다. 
i번째 줄의 j번째 값은 칸 (i, j)의 상태를 나타내며, 
이 값이 0인 경우 (i, j)가 청소되지 않은 빈 칸이고, 
1인 경우 (i, j)에 벽이 있는 것이다. 

방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 
로봇 청소기가 있는 칸은 항상 빈 칸이다.

3. 출력
로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

4. 문제 풀이
로봇의 방향이 친절하게도 0, 1, 2, 3으로 나오기 때문에
이를 index로 하는 dr, dc 리스트를 만들어 상하좌우 이동을 구현했다.

주의할 점은 범위 검사를 필수로 해 줄 것.
예시에는 가장자리 부분이 모두 1로 되어, 범위 검사를 안해도 오류가 나오지 않지만,
실제로는 가장자리 부분이 1이 아닌경우가 존재함

>>>코드

'''
14503번 로봇 청소기
입력 : n, m (방의 크기), r, c (로봇의 현위치)
d (로봇의 현 방향), room (방의 상태 n x m)
출력 : 청소하는 방의 개수

함수
1. robot() 로봇의 작동
input : r, c, d
output : cnt (청소한 칸의 개수)

2. check() 주변 4칸 검사
input : room, r, c
output : True/False 
'''

n, m = map(int, input().split())
r, c, d = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def robot(r, c, d):
    global cnt

    if room[r][c] == 0:
        cnt += 1
        room[r][c] = 2
    
    if check(r, c):
        for _ in range(4):
            d = (d+3) % 4
            if 0 <= r+dr[d] < n and 0 <= c+dc[d] < m and room[r+dr[d]][c+dc[d]] == 0:
                break
        robot(r+dr[d], c+dc[d], d)
    else:
        if room[r-dr[d]][c-dc[d]] != 1:
            robot(r-dr[d], c-dc[d], d)
        else:
            return
    
    
def check(r, c):
    if room[r+1][c] == 0 or room[r-1][c] == 0 or room[r][c+1] == 0 or room[r][c-1] == 0:
        return True
    return False

robot(r, c, d)
print(cnt)

5. 문제 링크
https://www.acmicpc.net/problem/14503

백준 파이썬 공부 2025.09.25
24416번 알고리즘 수업 - 피보나치 수 1

1. 문제
오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 
아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 
재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 
아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자.

피보나치 수 재귀호출 의사 코드는 다음과 같다.

fib(n) {
    if (n = 1 or n = 2)
    then return 1;  # 코드1
    else return (fib(n - 1) + fib(n - 2));
}

피보나치 수 동적 프로그래밍 의사 코드는 다음과 같다.

fibonacci(n) {
    f[1] <- f[2] <- 1;
    for i <- 3 to n
        f[i] <- f[i - 1] + f[i - 2];  # 코드2
    return f[n];
}

2. 입력
첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다.

3. 출력
코드1 코드2 실행 횟수를 한 줄에 출력한다.

4. 문제 풀이
피보나치 수가 아닌 각 코드의 실행 횟수를 출력한다

>>>코드

cnt1, cnt2 = 0, 0
def fib(n):
    global cnt1
    if (n == 1 or n == 2):
        cnt1 += 1
        return 1
    else:
        return fib(n-1) + fib(n-2)

f = [0, 1, 1]
def fibonacci(n):
    global cnt2
    if (n == 1 or n== 2):
        cnt2 += 1
        return f[n]
    for i in range(3, n+1):
        cnt2 += 1
        f.append(f[i-1] + f[i-2])
    return f[n]

n = int(input())
fib(n)
fibonacci(n)
print(cnt1, cnt2)

5. 문제 링크
https://www.acmicpc.net/problem/24416

백준 파이썬 공부 2025.09.24
14889번 스타트와 링크 (실버 1)

1. 문제
오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 
축구는 평일 오후에 하고 의무 참석도 아니다. 
축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 
이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 
아래와 같은 능력치를 조사했다. 

능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 

팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. 
Sij는 Sji와 다를 수도 있으며, 
i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

- 스타트 팀: S12 + S21 = 1 + 4 = 5
- 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

- 스타트 팀: S13 + S31 = 2 + 7 = 9
- 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 
위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 
스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

2. 입력
첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 
둘째 줄부터 N개의 줄에 S가 주어진다. 
각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. 
Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

3. 출력
첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

4. 문제 풀이
DFS를 이용해서 start와 link 팀의 점수를 계산하고, 점수의 차를 저장 후,
백트래킹하는 식으로 문제를 해결했다

>>> 시간초과

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

visited = [False] * n
answer = []

def DFS(depth):
    if depth == n//2:
        answer.append(calculation())
        return
    
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            DFS(depth+1)
            visited[i] = False

def calculation():
    start, link = 0, 0
    
    for i in range(n):
        for j in range(n):
            if visited[i] and visited[j]:
                start += ability[i][j]
            elif not visited[i] and not visited[j]:
                link += ability[i][j]
    
    return abs(start - link)
    
DFS(0)
print(min(answer))

시간초과가 나온다.
개선 방법이 여러가지가 있다.

1. input() 대신 sys.stdin.readline() 사용

2. DFS의 경우, 탐색을 시작할 지점을 저장해서 거기서부터 반복
DFS(start, depth) 형식으로 바꾸어 visited 탐색시 이전에 지나온 부분은 사용하지 않음
3개를 지정한다고 했을 시, (1, 2, 3) 이나 (2, 1, 3) 이나 (3, 2, 1)이나 점수의 합은 동일
따라서 순서가 중요하지 않기 때문에, 해당 숫자를 사용하였다면, 그 숫자 이상의 숫자만 고려하면 된다.

3.  calculation 함수 개선
calculation의 경우, 0~n-1까지의 이중 반복을 진행중인데, 
만약 visited[i][j] 와 visited[j][i]를 한번에 더한다면,
반복의 범위를 (0, n) (i, n)으로 줄일 수 있다.

>>>정답 코드

'''
14889번 스타트와 링크
초기 정보 : n의 값과 각자 조합에 따른 점수
출력 값: 만들 수 있는 능력치의 최소 차이

함수 DFS (가능한 연산 결과 모두 확인)
input start depth 
output 없음 (answer 배열에 결과 저장)

함수 calculation (인원에 따른 능력치 차이 계산)
input 없음
output result
'''
import sys
input = sys.stdin.readline
n = int(input())

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

visited = [False] * n
answer = []

def DFS(start, depth):
    if depth == n//2:
        answer.append(calculation())
        return
    
    for i in range(start, n):
        if not visited[i]:
            visited[i] = True
            DFS(i+1, depth+1)
            visited[i] = False

def calculation():
    start, link = 0, 0

    for i in range(n):
        for j in range(i+1, n):
            if visited[i] and visited[j]:
                start += ability[i][j] + ability[j][i]
            elif not visited[i] and not visited[j]:
                link += ability[i][j] + ability[j][i]
    
    return abs(start - link)
    
DFS(0, 0)
print(min(answer))

5. 문제 링크
https://www.acmicpc.net/problem/14889