해야만 한다

14501번 풀이 dp로 뒤에서부터 갱신하며 풀었다. 현재 날짜 + 소요시간이 퇴사일보다 크면 상담하지 않는다. = dp[i] = dp[i+1] 그게 아니라면 상담을 하고 (상담을 한 날 + 걸리는 시간) 까지의 dp값에 상담 보수를 더한 값과, 상담을 하지 않았을 때의 값을 비교하여 더 큰 쪽을 택한다. 코드 import sys input = sys.stdin.readline n = int(input()) sche = [list(map(int, input().split())) for _ in range(n)] dp = [0] * (n+1) for i in range(n-1, -1, -1): if sche[i][0]+i > n: dp[i] = dp[i+1] else: dp[i] = max(dp[i+1],..

문제 매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 세준이가 운전해야 하는 거리의 최솟값을 출력하시오. 입력 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다. 출력 세준이가 운전해야하는 거..

문제 n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 간선에는 가중치가 없다. 트리 T에 있는 각 정점에는 서로 다른 값이 부여된다. 트리 T에서 정점에 부여된 값이 k인 노드의 깊이(depth)를 출력하자. 루트 정점의 깊이는 0이고 자식 정점의 깊이는 부모 정점의 깊이보다 1만큼 더 큰 값을 갖는다. 입력 첫 번째 줄에 정점의 수 n과 정수 k가 공백을 사이에 두고 순서대로 주어진다. 두 번째 줄부터 n - 1개 줄에 걸쳐 간선의 정보가 주어진다. 한 줄에 하나의 간선 정보가 주어진다. 하나의 간선 정보는 부모 정점 번호 p와 자식 정점 번호 c가 공백을 사이에 두고 순서대로 주어진다. 다음 줄에는 0번 정점부터 n - 1번 ..

풀이 DP를 n*3의 2차원 형태로 만들어서 각 행의 RGB 비용을 모두 저장해둔다. DP[i] = [R비용,G비용,B비용] 이런식으로 갱신할 것이다. DP의 뼈대를 만들었다면 2중 for문을 통해 DP[i][j]에다가 i행의 특정 색상 비용 + i-1행의 나머지 색상 비용 중 작은 값을 더한 값을 넣는다. 현재 빨간색을 택했다면 이전의 파랑, 초록색 중 작은 값을 선택하고 더해서 넣는 셈 코드 import sys input = sys.stdin.readline n = int(input()) h = [list(map(int, input().split())) for _ in range(n)] dp = [[0] * 3 for _ in range(n)] for i in range(n): for j in ran..

풀이 순수한 구현 문제. 각 행위에 대한 함수들을 작성하고 한 사이클을 다 작성하면 while 문으로 원하는 값을 얻을 때까지 반복한다. 코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) temp = list(map(int,input().split())) arr = [] cnt = 0 for i in range(n): arr.append([temp[i]]) while 1: def fish_sort(): global cnt min_val = 10000 max_val = 0 for i in range(len(arr)): # 최소 찾아서 저장해두기 if arr[i][0] < min_val: min_val = arr[i][0] i..

풀이 ㅗ 모양이 아닌 블럭들은 dfs로 3번 탐색하면 만들 수 있는 모양들이다. ㅗ 모양은 일일이 for문을 작성해서 구했다. 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(n)] max_val = 0 visited = [[0]*m for _ in range(n)] dx, dy = [0,1,0,-1], [1,0,-1,0] def dfs(x,y,my_sum,cnt): global max_val if cnt == 4: max_val = max(max_val,my_sum) return for i in range(4): nx = x..

풀이 큐에 불을 모두 넣고 지훈이를 마지막에 append 하여 bfs 탐색 불은 벽이 아닌 것들을 모두 'F'로 바꾸고 지훈이는 visited 배열에 이동 거리를 누적해간다. 탈출구 (배열의 끝부분) 에 도달하면 탐색을 종료하고 이동 거리를 출력한다. bfs가 끝났는데 탈출구에 도달하지 못했다면 IMPOSSIBLE을 출력한다. 코드 from collections import deque import sys input = sys.stdin.readline r,c = map(int, input().split()) dx, dy = [0,1,0,-1], [1,0,-1,0] visited = [[0]*c for _ in range(r)] maze = [list(input().rstrip()) for _ in ran..

문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. ..