문제

Baekjoon 2156: 포도주 시식

• 설명: 포도주가 일렬로 놓아져있고, 세개 연속으로 먹지 못할 때 최대로 먹을 수 있는 양울 구하라

풀이

• i번째 포도주를 먹을 때는 i - 1, i - 2, i - 3번째 포도주를 먹을 때 먹을 수 있는 가장 큰 양을 먹고 먹으면 된다
• 이때 i - 1번째 포도주는 그 이전 포도주를 먹었으면 안되기 때문에, DP 테이블에 2가지 종류 (이전 포도주를 먹었는지, 안먹었는지)를 저장해준다

오늘의 회고

• i - 3 번째 포도주를 먹어야된다는 사실을 깜빡하고 계속 틀렸었다.

Code

n = int(input())
wine = [int(input()) for _ in range(n)]

dp = [
    [0 for _ in range(n)],
    [0 for _ in range(n)]
]
dp[0][0] = dp[1][0] = wine[0]

ans = wine[0]
if n > 1:
    dp[0][1] = wine[1]
    dp[1][1] = wine[0] + wine[1]
    ans = max(ans, dp[0][1], dp[1][1])

    for i in range(2, n):
        if i > 2:
            dp[0][i] = max(dp[0][i - 2], dp[1][i - 2], dp[0][i - 3], dp[1][i - 3]) + wine[i]
        else:
            dp[0][i] = max(dp[0][i - 2], dp[1][i - 2]) + wine[i]
        dp[1][i] = dp[0][i - 1] + wine[i]

        ans = max(ans, dp[0][i], dp[1][i])

print(ans)

필수 해시태그: #99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL

문제

Baekjoon 16401: 과자 나눠주기

• 설명: 과자들의 크기가 주어졌을 때 M개를 넘도록 과자를 자를 수 있는 최대 길이를 구하여라

풀이

• 과자를 1로 자르면 거의 대부분의 테스트 케이스에서 가능하다
• 이렇게 숫자를 늘려나가다보면 언젠가 부터 모든 학생들에게 나눠줄 수 없어지는 첫 길이가 생기게 된다.
• 우리는 이 경계를 찾으면 되는데 숫자의 범위가 굉장히 크고, 범위가 이분법적으로 나누어져있기 때문에 이진탐색을 사용하여 찾아준다.

오늘의 회고

• 오랜만에 풀어보는 이진탐색이지만 확실히 개념을 익혀두니 쉽게 잊어먹지 않는 것 같다.

Code

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

def get_num(size):
    result = 0
    for s in snack:
        result += s // size

    return result

left, right = 0, 1_000_000_000
while left + 1 < right:
    mid = (left + right) // 2

    if get_num(mid) >= m:
        left = mid
    else:
        right = mid

print(left)

문제

Baekjoon 1783: 병든 나이트

• 설명: 오른쪽으로 4방향으로 이동하는 나이트가 있을 때 주어진 체스판에서 가장 많이 움직일 수 있는 칸을 구하여라

풀이

• 주어진 조건
  1. 나이트는 오른쪽으로만 움직인다.
  2. 4번 이상 움직이기 위해서는 4가지 움직임을 모두 써야한다.
• 도출할 수 있는 사실
  1. 세로의 크기는 3 이상이면 위아래 움직임을 상쇄시키면서 오른쪽으로 움직일 수 있으므로 세로의 크기는 1, 2, 3 세가지만 고려하면된다.
  2. 가로의 크기가 7 (2 + 2 + 1 + 1) 이상이면 4가지 움직임을 모두 쓸 수 있다.
• 정리
  • 위의 제한 조건 안에서는 경우의 수를 따져서 값을 구한다.
  • 제한 조건을 넘어서는 부분에서는 (위 2, 오 1), (아 2, 오 1)로 반복해서 움직이면 최대한 많은 칸을 움직일 수 있다.
  • 따라서 4번 움직인 뒤 (총 5번 움직인 것) 남은 가로 칸을 1칸씩 움직이면 된다 ($m - 7$)

오늘의 회고

• 오른쪽으로는 무한히 증가해야만 한다는 점에서 위의 규칙을 도출 할 수 있었다.
• 조건을 굉장히 상세하게 짰지만 더 간단하게 수식으로 표현할 수 있을 것 같다.

Code

# Baekjoon01783.py
n, m = map(int, input().split())


if n == 1:
    ans = 1
elif n == 2:
    if m < 3:
        ans = 1
    elif m < 5:
        ans = 2
    elif m < 7:
        ans = 3
    else:
        ans = 4
else:
    if m == 1:
        ans = 1
    elif m == 2:
        ans = 2
    elif m == 3:
        ans = 3
    elif m <= 6:
        ans = 4
    else:
        ans = 5 + (m - 7)

print(ans)

필수 해시태그: # # # # #

문제

Baekjoon 9996: 한국이 그리울 땐 서버에 접속하지

• 설명: 주어진 패턴과 일치하는 문자열을 찾아라

풀이

• *은 무조건 가운데 1개만 나오기 때문에 단순히 * 기준 왼쪽/오른쪽이 주어진 파일 이름의 왼쪽/오른쪽과 정확히 일치하는지 판단하면 된다.

오늘의 회고

• 문자열 슬라이싱 간 인덱스를 넘어가면 오류가 뜰 줄 알았는데 뜨지 않는다!

Code

# Baekjoon09996.py
import sys
input = sys.stdin.readline

t = int(input())

pattern = input().rstrip()
prefix, postfix = pattern.split('*')

n, m = len(prefix), len(postfix)

for _ in range(t):
    name = input().rstrip()
    if n + m > len(name):
        print("NE")
    else:
        if name[:n] == prefix and name[-m:] == postfix:
            print("DA")
        else:
            print("NE")

문제

Baekjoon 10799: 쇠막대기

• 설명: 쇠막대기를 잘랐을 떄 잘리는 막대기의 개수를 구하여라

풀이

• ()가 동시에 나타나면 이전까지 (의 개수만큼 막대기가 잘린다.
• )와 맞는 (가 연속되어있지 않다면 해당 막대기가 끝인 것이므로 단순히 1을 더해준다.
• 이를 스택으로 구현하여서 ()라면 stack의 크기를 더해주고,
  • )를 만났다면 1을 더해주고, 스택에서 가장 최근 (를 빼주며
  • (를 만났다면 단순히 push 해준다
• 이는 사실상 (만 넣어줄 것이기 때문에 실제 스택을 구현하지 않고 단순히 숫자만 늘려가면 된다.

오늘의 회고

• 문제를 대충보고 생각했을 떄는 생각이 나지 않았지만, ()가 무조건 레이저라는 것을 보고 바로 이를 따로 처리해줘야한다고 생각하였다.
• 만약 )가 혼자 있을 경우를 처리하지 못해서 틀렸었지만, 이 경우에 단순히 1만 더해주면 된다는 것을 깨닫고 문제를 풀 수 있었다.

Code

# Baekjoon10799.py
brackets = input()

n = len(brackets)

ans, stck = 0, 0

i = 0
while i < n:
    if brackets[i] == '(':
        if i + 1 < n and brackets[i + 1] == ')':
            ans += stck
            i += 1
        else:
            stck += 1
    else:
        ans += 1
        stck -= 1

    i += 1

print(ans)

문제

Baekjoon 4963: 섬의 개수

• 설명: 1과 0으로 이루어진 그래프가 주어질 때 1로 이루어진 영역의 개수를 세어라

풀이

• 모든 점을 탐색하며 방문하지 않은 점부터 시작해서 그 점과 이어진 점들을 탐색하며 하나로 이어준다.
• 총 이어진 점의 덩어리 개수를 세어준다.

오늘의 회고

• 오랜만에 대각선 탐색을 하게된 것 같다.
• 더더욱 나만의 코딩 스타일이 확고해지는 것 같다.

Code

# Baekjoon04963.py
import sys
input = sys.stdin.readline

MOVES = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

def dfs(row, col):
    for r, c in MOVES:
        nextRow, nextCol = row + r, col + c

        if (0 <= nextRow < maxRow) and (0 <= nextCol < maxCol):
            if not visited[nextRow][nextCol] and adjMat[row][col]:
                visited[nextRow][nextCol] = True

                dfs(nextRow, nextCol)

maxCol, maxRow = map(int, input().split())
while (maxCol != 0 and maxRow != 0):
    ans = 0
    visited = [[False] * maxCol for _ in range(maxRow)]

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

    for row in range(maxRow):
        for col in range(maxCol):
            if not visited[row][col] and adjMat[row][col]:
                visited[row][col] = True
                dfs(row, col)

                ans += 1

    print(ans)

    maxCol, maxRow = map(int, input().split())

문제

Baekjoon####: 수열

• 설명: 연속된 k일 간의 온도의 합을 최대로 만들어라

풀이

1. 변수를 탐색하며 온도의 값을 더해간다.
2. 만약 지금까지 더한 일수가 k라면 정답과 현재 온도의 합 중 큰 값을 저장한다.
   • 이후 가장 앞의 일자의 온도를 뺴준다.

• 이렇게하면 정확히 k개의 온도의 합을 $O(n)$만에 유지할 수 있게된다.

오늘의 회고

• 투 포인터를 활용하여 슬라이딩 윈도우를 구현하는 문제이다.
• 오랜만에 슬라이딩 윈도우를 구현하니 옛날 기억이 새록새록 났다.

Code

# Baekjoon02559.py
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
arr = list(map(int, input().split()))

ans = -0x3f3f3f3f
curr = [0, 0]
for i in range(n):
    curr[0] += arr[i]
    curr[1] += 1

    if curr[1] == k:
        ans = max(ans, curr[0])
        curr[0] -= arr[i - (k - 1)]
        curr[1] -= 1

print(ans)

문제

Baekjoon 2468: 안전 영역

• 설명: 영역의 높이가 주어질 때, 안전 영역의 개수를 최대화 하라.

풀이

• 비의 양이 100이 넘어가면 당연히 최대 높이를 넘어가기에 100까지만 비가 온다고 생각해보면

• 모든 위치는 $100 \times 100$개 이고 이를 $0 ~ 100$의 강수량에 따라 안전지역을 Bruteforce로 찾으면

• 충분히 시간 내에 안전지역을 찾을 수 있다.

• 안전지역을 찾는 것은 현재 주어진 강수량을 기준으로 더 큰 값들이 이어지는 개수를 세준다.

  • 이렇게 DFS, BFS를 통해 그래프에서 이어진 부분을 탐지한 후 안전지역의 숫자를 늘려준다.

오늘의 회고

• 모든 지역의 높이가 1이고 비가 하나도 오지 않을 때 답은 1이지만,
• 비가 무조건 올 것이라고 생각하여서 이 경우 1을 반환하여서 틀렸었다.
• 조금 더 엄밀하게 엣지 케이스를 생각하면서 풀어야겠다

Code

# Baekjoon02468.py
import sys
input = sys.stdin.readline

sys.setrecursionlimit(1_000_000)

MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]

n = int(input())

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

def get_safe_area(rain):
    visited = [[False] * n for _ in range(n)]

    def dfs(curr):
        for i, j in MOVES:
            new_row, new_col = curr[0] + i, curr[1] + j

            if (0 <= new_row < n) and (0 <= new_col < n):
                if not visited[new_row][new_col] and area[new_row][new_col] > rain:
                    visited[new_row][new_col] = True
                    dfs((new_row, new_col))

    result = 0
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and area[i][j] > rain:
                visited[i][j] = True
                dfs((i, j))

                result += 1

    return result

ans = 0
for i in range(0, 101):
    ans = max(ans, get_safe_area(i))

print(ans)