시나위

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().split()) matrix = [input() for _ in range(N)] visit = [[0] * M for _ in range(N)] def bfs(r, c): q = deque() q.append((r, c)) visit[r][c] = 1 delta = [(-1, 0..

www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net n = int(input()) wine = [0] + [int(input()) for _ in range(n)] dp = [0] * (n + 1) # 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. # 최대 두잔 연속 dp[1] = wine[1] if n >= 2: dp[2] = max(wine[1]+wine[2], dp[0] + wine[2]) for i in range(3, n + 1): dp[i] = ma..

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net n = int(input()) arr = [0] + list(map(int, input().split())) dp = [0] * (n + 1) for i in range(1, n + 1): max_val = 0 for j in range(i): if arr[j] < arr[i] and max_val < dp[j]: max_val = ..

programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr def solution(triangle): dp = [[0] * i for i in range(1, len(triangle) + 1)] dp[0][0] = triangle[0][0] for i in range(1, len(dp)): for j in range(len(dp[i])): if j == 0: dp[i][j] = triangle[i][j] + dp[i - 1][j] elif j == len(dp[i]) - 1: dp[i][j] = triangl..

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net import sys from heapq import heappop, heappush input = sys.stdin.readline N, E = map(int, input().split()) K = int(input()) link = [list() for _ in range(N + 1)] for _ in range(E): n1, n2, w = map(int, input().split(..

programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 대회 당일에는 트리로 만들면 될거같긴한데 그이후에 어떻게 접근해야할지 몰랐다. if sum(a): return -1 만 해놓고 그이후엔 트리로 풀면되지 않을까하고 뚱땅뚱땅하긴했지만 33점인가 나왔다. a = [0,-5,2,1,2] edges = [[0,1],[3,4],[2,3],[0,3]] def solution(a, edges): # sum이 0이 아니면 ..

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] def backtrack(inboard, inred, inblue, ind=0): global result, cnt, delta # if result == 1: # return if ind == 10: return else: for i in range(4): tmp_board = [in..

www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] def backtrack(inboard, inred, inblue, ind=0, arr=[]): global result, delta if result == 1: return if ind == 10: return else: for i in range(4): tmp_board = [inboa..

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net n = int(input()) dp = [[0] * 10 for _ in range(101)] for i in range(1, 10): dp[1][i] = 1 for i in range(2, n + 1): for j in range(10): if j == 0: dp[i][j] = dp[i - 1][1] elif j == 9: dp[i][j] = dp[i - 1][8] else: dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] print(sum(dp[n]) % 1000000000) dp[5]..

www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net n = int(input()) stair = [0] + [int(input()) for _ in range(n)] if n == 1: print(stair[-1]) else: dp = [0] * (n + 1) dp[0] = stair[0] dp[1] = max(stair[0] + stair[1], stair[1]) dp[2] = max(stair[0] + stair[2], stair[1] + stair[2]) for i i..