문제

Baekjoon 17265: 나의 인생에는 수학과 함께

• 설명: 주어진 보드판에서 아래쪽, 오른쪽으로만 이동할 수 있을 때 최솟값, 최댓값을 구하여라

풀이

• n이 $5$라서 모든 경우의 수를 다 따지면 된다.

오늘의 회고

• 오늘 역시 잔실수가 많았다. 가장 적은 값이 음수가 될수 있었는데 최댓의 초깃값을 0으로 두어서 반례를 찾는데 한참 걸렸다.
• 이외에도 다음줄에 출력하는게 아닌데 다음줄에 출력한다든가 등 문제가 많았다.
• 더 집중해서 풀어보자

Code

// Baekjoon17265.cpp
#include <iostream>

#include <string>

using namespace std;

using pii = pair<int, int>;

const int moves[2][2] = { { 1, 0 }, { 0, 1 } };

int n;
char map[5][5];
pii ans = { -0x3f3f3f3f, 0x3f3f3f3f };

int getValue(string expr) {
    int prev = expr[0] - '0';
    for (int i = 1; i < expr.size(); i += 2) {
        if (expr[i] == '+')
            prev += expr[i + 1] - '0';
        else if (expr[i] == '-')
            prev -= expr[i + 1] - '0';
        else
            prev *= expr[i + 1] - '0';
    }

    return prev;
}

void dfs(int row, int col, string expr) {
    if (row == (n - 1) && col == (n - 1)) {
        ans.first = max(ans.first, getValue(expr));
        ans.second = min(ans.second, getValue(expr));
    } else {
        for (int i = 0; i < 2; i++) {
            int nextRow = row + moves[i][0], nextCol = col + moves[i][1];
            if ((0 <= nextRow && nextRow < n) && (0 <= nextCol && nextCol < n)) {
                expr.push_back(map[nextRow][nextCol]);
                dfs(nextRow, nextCol, expr);
                expr.pop_back();
            }
        }
    }
}

int main(void) {
    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];

    string expr;
    expr.push_back(map[0][0]);
    dfs(0, 0, expr);

    cout << ans.first << ' ' << ans.second << '\n';

    return 0;
}

문제

Baekjoon 28069: 김밥천국의 계단

• 설명: 2가지 행동 중 하나를 선택해서 K번 행동하여 N번째 계단에 도달할 수 있는지 판단하여라

풀이

• $0$번째 계단에서 지팡이를 두드리면 $0 + \lfloor \frac{0}{2} \rfloor = 0$이므로 제자리 걸음을할 수 있다.
• 기본적으로 $0$번째 계단에서 BFS를 통해 모든 계단까지의 최단거리를 구할 수 있다.
• 이때 N번째 계단에 도달하기 위한 최소 행동이 A라면, A - K만큼 $0$번째 계단에서 제자리 걸음한 후 이동한다면 무조건 K번째 행동에 N번째 계단에 도달할 수 있다.
• 하지만 만약 A가 K보다 크다면 최단 행동으로도 K번째에 도달하지 못한다는 뜻이므로 이 경우 우리는 김밥을 먹을 수 없다.

오늘의 회고

• 가장 기본적인 BFS 문제인 것 처럼 보이지만, 정확히 K번째에 도달해야하므로 쉽사리 풀지 못하고 헤맸었다.
• 하지만 결국 최단경로로 움직이기 전에 제자리걸음을 하면 K번째에 도달할 수 있다는 것을 깨닫고 바로 구현에 들어갔다.
• 한개의 조건만으로 기존 문제를 아주 잘 응용한 문제인 것 같아 재밌게 풀었다. 좋은 문제다.

Code

# Baekjoon28069.py
from collections import deque

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

q = deque()
visited = [False for _ in range(n + 1)]

q.append((0, 0))
visited[0] = True
while q:
    vertex, distance = q.popleft()

    if vertex == n:
        ans = distance
        break

    next_v = vertex + 1
    if next_v <= n and not visited[next_v]:
        visited[next_v] = True
        q.append((next_v, distance + 1))

    next_v = vertex + vertex // 2
    if next_v <= n and not visited[next_v]:
        visited[next_v] = True
        q.append((next_v, distance + 1))

print("minigimbob" if ans <= k else "water")

문제

Baekjoon 27971: 강아지는 많을수록 좋다

• 설명: 호무라가 강아지를 한번에 A, B 마리를 생성할 수 있고 특정 구간의 강아지 수를 만족한다면 모든 강아지는 사라진다. 이떄 N마리의 강아지를 생성하기 위한 최소 마법의 수를 구하여라

풀이

• 닫힌 구간을 미리 모두 저장해두고 A, B마리를 생성해주며 시뮬레이션 해준다.
• 이떄 가장 최소 마법의 수를 구하는 문제이기 떄문에 BFS를 사용하여 문제를 풀어준다.

오늘의 회고

• True를 False로 두는 둥 잔실수가 많았다. 더 노력하자!

Code

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

from collections import deque

n, m, a, b = map(int, input().split())
delete = [False for _ in range(100_001)]

for _ in range(m):
    l, r = map(int, input().split())

    for i in range(l, r + 1):
        delete[i] = True

q = deque()
visited = [False for _ in range(100_001)]

q.append((0, 0))
visited[0] = True

ans = -1
while q:
    curr, time = q.popleft()
    if curr == n:
        ans = time
        break

    next_dog = curr + a
    if next_dog <= 100_000 and (not visited[next_dog]) and (not delete[next_dog]):
        visited[next_dog] = True
        q.append((next_dog, time + 1))

    next_dog = curr + b
    if next_dog <= 100_000 and (not visited[next_dog]) and (not delete[next_dog]):
        visited[next_dog] = True    
        q.append((next_dog, time + 1))

print(ans)

필수 해시태그: # #코딩테스트준비 # # #

문제

Baekjoon 18126: 너구리 구구

• 설명: 트리가 주어질 때 루트에서 거리가 가장 먼 노드까지의 거리를 찾아라

풀이

• $N$개의 노드가 있고, $N - 1$개의 간선이 있으며 모든 노드가 연결되어있으려면 반드시 트리 구조이다.
• 따라서 입구($1$)에서 가장 먼 위치는 단순히 모든 노드를 탐색하며 가장 먼 위치에 있는 노드까지의 거리를 구하면 된다.

오늘의 회고

• setrecursionlimit을 해두지 않아 틀렸었다.
• python 기본 재귀 깊이는 1,000이기 때문에 문제에서 주어진 5,000개의 노드를 탐색하기엔 부족하다.

Code

import sys
sys.setrecursionlimit(10_000)
input = sys.stdin.readline


def dfs(me, mom, dis):
    global ans

    ans = max(ans, dis)
    for adj_v, adj_d in adj_list[me]:
        if adj_v != mom:
            dfs(adj_v, me, dis + adj_d)


n = int(input())

adj_list = [[] for _ in range(5_001)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())

    adj_list[a].append((b, c))
    adj_list[b].append((a, c))

ans = 0
dfs(1, 0, 0)

print(ans)

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

문제

Programmers: 신규 아이디 추천

• 설명: 주어진 조건대로 아이디를 파싱하여라

풀이

• 문제에서 주어진 단계대로 구현하면 된다.

오늘의 회고

• 주어진대로 구현하였지만 잔실수가 많아서 에러가 많이 발생하였다.
• 구현 문제를 다시 열심히 풀어 잔실수를 줄여야할 필요가 있겠다.

Code

# Programmers72410.py
def solution(new_id):
    # step 1
    new_id = new_id.lower() 

    new_char = []
    for c in new_id:
        # step 2
        if c in 'abcdefghijklmnopqrstuvwxyz0123456789-_': 
            new_char.append(c)
        # step 3
        elif c == '.':
            if len(new_char) == 0 or new_char[-1] != '.': 
                new_char.append(c)

    # step 4
    n = len(new_char)

    i = 0
    while i < n and new_char[i] == '.':
        i += 1

    j = n - 1
    while j >= 0 and new_char[j] == '.':
        j -= 1

    new_char = new_char[i:j + 1] 

    # step 5
    if len(new_char) == 0: 
        new_char = ['a']

    # step 6
    if len(new_char) > 15: 
        new_char = new_char[:15]

    n = len(new_char)
    j = n - 1
    while j >= 0 and new_char[j] == '.':
        j -= 1
    new_char = new_char[:j + 1] 

    # step 7
    while len(new_char) <= 2:
        new_char.append(new_char[-1])

    return ''.join(new_char)

문제

Baekjoon 17271: 리그 오브 레전설 (Small)

• 설명: A 스킬이 $1$초, B 스킬이 $M$초 걸릴 때 $N$초 동안 가능한 스킬 조합의 수를 구하여라

풀이

• N초 동안 가능한 스킬 조합의 수는 아래의 합과 같다
  • $(N - 1)$초 동안 가능한 스킬 조합에 A 스킬을 1번 더 쓰거나
  • $(N - M)$초 동안 가능한 스킬 조합에 B 스킬을 1번 더 쓰거나
• 따라서 DP를 사용하여 문제를 풀어준다.

오늘의 회고

• 피보나치에서 한 단계 나아간 대표적인 DP 문제이다!
• 문제 번호가 회문이다!

Code

MOD = 1_000_000_007

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

dp = [1]
for i in range(1, n + 1):
    dp.append(dp[i - 1])
    if i >= m:
        dp[i] += dp[i - m]
    dp[i] %= MOD

print(dp[n])

문제

Baekjoon 17484: 진우의 달 여행 (Small)

• 설명: 이전과 동일한 방법으로 이동하지 못할 때 최소한으로 지구에서 달까지 이동하는 비용을 구하여라

풀이

• n이 충분히 작기 때문에 단순히 모든 경우의 수를 구하며 가장 비용이 적게 발생하는 경로의 비용을 찾았다.
• 그래프 형식처럼 보여 dfs로 구현하였고 이때 이전에 이동한 위치를 인자로 넣어주어 동일하게 이동하지 않게 하였다.
• 단순하게 생각하면 모든 위치에서 3가지 방향으로 나갈 수 있고 n x m이기 때문에 시간복잡도는 $O(3^n \cdot m)$이다.

오늘의 회고

• 다 풀고 알고리즘 분류를 보니 DP가 있었다.
• 이전에 그 위치로 이동한 방향, 해당 위치를 인덱스, 값을 비용의 최소값으로 3차원 배열로 두면 DP로 풀 수 있다.

Code

# Baekjoon17484.py
MOVES = [-1, 0, 1]

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

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

def dfs(row, col, prev, curr):
    if row == n - 1:
        return curr

    result = 0x3f3f3f3f

    new_row = row + 1
    for i in range(len(MOVES)):
        new_col = col + MOVES[i]
        if prev != i and (0 <= new_row < n and 0 <= new_col < m):
            result = min(result, dfs(new_row, new_col, i, curr + mat[new_row][new_col]))

    return result

ans = 0x3f3f3f3f
for i in range(m):
    ans = min(ans, dfs(0, i, -1, mat[0][i]))

print(ans)

문제

Programmers: JadenCase 문자열 만들기

• 설명: 문자열이 주어질 때 JadenCase로 변경하여라

풀이

• 공백을 만났다면 그 다음 첫 문자는 대문자로 변경한 뒤 공백을 만나기 전까지 모두 소문자로 변경해주면 된다.

오늘의 회고

• 공백을 기준으로 split을 하려했지만 2개인 경우를 어떻게 처리할까 고민하다 그냥 구현해버렸다!

Code

# Programmers12951.py
def solution(s):
    n = len(s)

    ans = ''

    is_capital = True
    for i in range(n):
        temp = ''
        if s[i] == ' ':
            temp = ' '
            is_capital = True
        elif is_capital:
            temp = s[i].upper()
            is_capital = False
        else:
            temp = s[i].lower()

        ans += temp

    return ans