알고리즘

포도주 시식[백준 2156] - python

import sys input = sys.stdin.readline def BOJ2156() : n = int(input()) dp = [[0 for _ in range(3)] for _ in range(n)] l = [] for _ in range(n) : l.append(int(input())) # dp[i][0] = 해당 잔을 마시지 않은 경우 # dp[i][1] = 앞의 잔을 마시지 않고 해당 잔을 마신 경우 # dp[i][2] = 앞의 잔을 마시고 해당 잔을 마신 경우 dp[0] = [0, l[0], l[0]] for i in range(1, n) : dp[i][0] = max(dp[i-1]) dp[i][1] = dp[i-1][0] + l[i] dp[i][2] = dp[i-1][1] + l[i]..

연속합 [백준 1912] - python

import sys input = sys.stdin.readline def BOJ1912() : n = int(input()) l = list(map(int, input().split())) dp = list(l) for i in range(1, n) : dp[i] = max(dp[i-1] + l[i], l[i]) print(max(dp)) BOJ1912() 1. 연속된 숫자들의 합중 최댓값을 구하면 된다. 이전 까지의 합을 이용해야 하므로 dp를 적용하였다. 2. 수를 한 개이상 무조건 선택해야 하므로 입력받은 배열을 그대로 dp배열로 넣어주었다. 3. 해당 칸을 선택하거나 선택하지 않는 경우가 있을수 있다. 선택한 경우와 선택하지 않은 경우중 큰 값을 가지고 가게 하였다. https://www.acm..

계단 오르기 [백준 2579] - python

# 풀이 1번 import sys input = sys.stdin.readline def BOJ2579(): n = int(input()) stairs = [0 for _ in range(301)] for i in range(n): stairs[i] = int(input()) dp = [0 for _ in range(301)] dp[0] = stairs[0] dp[1] = stairs[0] + stairs[1] dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2]) # 마지막 칸은 꼭 밟아야 한다. 전칸을 밟을 경우와 밟지 않은경우가 있을것이다. for i in range(3, n) : dp[i] = max(dp[i-3] + stairs[i-1] + sta..

게임 개발[백준 1516] - python

import heapq import sys input = sys.stdin.readline def BOJ1516() : N = int(input()) time = [0 for _ in range(N+1)] graph = [[] for _ in range(N+1)] indegree = [0 for _ in range(N+1)] queue = [] result = [0 for _ in range(N+1)] for i in range(1, N + 1) : temp = list(map(int, input().split())) time[i] = temp[0] temp_graph = temp[1:-1] indegree[i] = len(temp_graph) for k in temp_graph : graph[k].ap..

작업 [백준 2056] - python

import heapq import sys input = sys.stdin.readline INF = 1e6 + 1 def BOJ2056() : N = int(input()) time = [0] graph = [[] for _ in range(N+1)] indegree = [0 for _ in range(N+1)] queue = [] for i in range(N) : temp = list(map(int, input().split())) time.append(temp[0]) if len(temp) > 2 : indegree[i+1] = len(temp[2:]) for k in temp[2:] : graph[k].append(i+1) for i in range(1, N+1) : if indegree[i] ..

문제집 [백준 1766] - python

import heapq import sys input = sys.stdin.readline # 번호가 작은 문제를 먼저 풀어야 하므로 heapq를 사용하자 def BOJ1766() : N, M = map(int, input().split()) count_of_line = [0] * (N+1) graph = [[] for _ in range(N+1)] heap = [] result = [] for _ in range(M) : a, b = map(int, input().split()) count_of_line[b] += 1 graph[a].append(b) for i in range(1, N+1) : if count_of_line[i] == 0 : heapq.heappush(heap, i) while hea..

음악프로그램 [백준 2623] - python

import sys input = sys.stdin.readline def BOJ2623() : N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] count_of_line = [0] * (N+1) queue = [] answer = [] for _ in range(M) : temp = list(map(int, input().split())) _, b = temp[:2] temp_list = temp[2:] for i in temp_list : graph[b].append(i) count_of_line[i] += 1 b = i for i in range(1, N+1) : if count_of_line[i] == 0 : queue.appen..

줄 세우기[백준 2252] - python

import sys input = sys.stdin.readline def BOJ2252() : N, M = map(int, input().split()) count_of_line = [0] * (N+1) graph = [[] for _ in range(N+1)] queue = [] for _ in range(M) : A, B = map(int, input().split()) count_of_line[B] += 1 graph[A].append(B) for i in range(1, N+1) : if count_of_line[i] == 0 : queue.append(i) while queue : student = queue.pop(0) for i in graph[student] : count_of_line[..

단지번호붙이기 [백준 2667] - python

import sys input = sys.stdin.readline def BOJ2667() : global graph global N direction = [[1, 0], [-1, 0], [0, 1], [0, -1]] def dfs(x, y, type) : stack = [] stack.append([x, y]) count = 1 while stack : curr_x, curr_y = stack.pop() for dir in direction : dir_x, dir_y = dir next_x = dir_x + curr_x next_y = dir_y + curr_y if 0

맥주 마시면서 걸어가기

from collections import deque import sys input = sys.stdin.readline LENGTH = 65536 HALF_LENGTH = 32768 INF = 1e6 def BOJ9205() : global convenient_and_target global pentaport_x, pentaport_y def bfs(curr_x, curr_y, beer) : queue = deque() visit = [] queue.append([curr_x, curr_y, beer]) visit.append([curr_x, curr_y, beer]) while queue : curr_x, curr_y, curr_beer = queue.popleft() if curr_x == pent..