본문 바로가기

전체 글173

[DP] python 1890 점프 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net # 2023.01.29 import sys input = sys.stdin.readline n = int(input()) game = [list(map(int, input().split())) for _ in range(n)] dp = [[0]*(n) for _ in range(n)] # 경우의 수 dp[0][0]=1 for i in range(n): for j in range(n): .. 2023. 1. 29.
[DP] python 11048 이동하기 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net # 2023.01.29 import sys input = sys.stdin.readline n, m = map(int, input().split()) maze = [list(map(int, input().split())) for _ in range(n)] dp = [[0]*(m+1) for _ in range(n+1)] for i in range(1, n+1): for j in ra.. 2023. 1. 29.
[DP] python 2294 동전2 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net # 2023.01.28 import sys input = sys.stdin.readline n, k = map(int, input().split()) value = [int(input()) for _ in range(n)] dp=[10**9]*(k+1) # 동전의 개수 dp[0]=0 # 0은 동전을 0개 선택함 for v in value: # 동전의 가치 for in.. 2023. 1. 29.
[Recursion] 11057 오르막수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net # 2023.01.28 import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) # A 2023. 1. 29.
[DP] python 10844 쉬운 계단 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net # 2023.01.29 import sys input = sys.stdin.readline n = int(input()) # 자리수 dp=[[0]*(10) for _ in range(n+1)] for j in range(1, 10): dp[1][j]=1 for i in range(2, n+1): for j in range(10): if j==0: dp[i][j]=dp[i-1][j+1] elif j==9: dp[i][j]=dp[i-1][j-1] else: dp[i][j]=dp[i-1][j-1]+dp[i-1][j+.. 2023. 1. 29.
[DP] python 2293 동전1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net # 2023.01.28 import sys input = sys.stdin.readline n, k = map(int, input().split()) # n가지 종류,가치의 합 k원 value = [int(input()) for _ in range(n)] dp=[0]*(k+1) # dp의 index: 가치의 합, value: 경우의 수 dp[0]=1 # 가치의 합이 0: 동전을 하나도 쓰지 않는 경.. 2023. 1. 28.
[BFS] python 2573 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net # 2023.01.28 import sys input = sys.stdin.readline from collections import deque n, m = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] ice=[] for i in range(n): for j in range(m): i.. 2023. 1. 28.
[BFS] 9205 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net # 2023.01.27 import sys input = sys.stdin.readline from collections import deque def bfs(startX, startY, store, endX, endY): visited=[False]*(len(store)) # 편의점 방문 check q = deque([[startX, startY]]) while q: a, b = q.pop.. 2023. 1. 27.
[BFS] python 14503 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net # 2023.01.26 import sys input = sys.stdin.readline from collections import deque n, m = map(int, input().split()) # 세로, 가로 r, c, d = map(int, input().split()) # 좌표, 바라보는 방향 {0: 북쪽, 1: 동쪽, 2: 남쪽, 3: 서쪽} graph = [list(map(in.. 2023. 1. 26.
[BFS] python 2468 안전 영역 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net # 2023.01.25 import sys input=sys.stdin.readline from collections import deque n = int(input()) graph=[] maxDepth = 0 for i in range(n): graph.append(list(map(int, input().split()))) maxDepth = max(maxDepth, max(graph[i])) # 물이.. 2023. 1. 25.
[BFS] python 5014 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net # 2023.01.24 import sys input = sys.stdin.readline from collections import deque # 총 f층, 지금 s층, 원하는 g층, 위로 u층 이동, 아래로 d층 이동 f, s, g, u, d = map(int, input().split()) visited=[False]*(f+1) # 방문여부 stair=[0]*(f+1) queue=deque() # 너비 .. 2023. 1. 24.
[DFS] python 2644 촌수계산 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net # 2023.01.23 import sys input = sys.stdin.readline n = int(input()) a, b = map(int, input().split()) # start, end m = int(input()) graph = [[] for _ in range(n+1)] # n명의 사람들 for _ in range(m): x, y = map(int, inp.. 2023. 1. 23.

티스토리툴바