https://www.acmicpc.net/problem/17396import sysimport heapqinput = sys.stdin.readlinelooks = []INF = sys.maxsizen, m = map(int, input().split())looks = list(map(int, input().split()))graph = [[] for _ in range(n+1)]distance = [INF] * (n+1)looks[n-1] = 0for i in range(m): a, b, t = map(int, input().split()) graph[a].append((b, t)) graph[b].append((a, t)) def dijk(start): q = [] ..
코테/백준 문제풀이
https://www.acmicpc.net/problem/2665 다익스트라 이용문제에서는 흰색(지나갈 수 있는 곳)을 1, 검은색을 0으로 해줬는데 입력받은 뒤 이를 완전히 뒤집고 다익스트라 알고리즘을 통해 (N,N)으로 갈 수 있는 최단거리를 구해주면 끝import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)rooms = []n = int(input())distance = [[INF] * n for _ in range(n)]dx = [1, -1, 0, 0]dy = [0, 0, 1, -1]for i in range(n): strarr = input().strip() room = [(int(ch) ^ 1) for ch in strarr] ..
https://www.acmicpc.net/problem/11057n = int(input())dp = [[0] * (10) for _ in range(n+1)]dp[1][0] = 1for i in range(1, 10): dp[1][i] = 1 + dp[1][i-1]if n > 1: for i in range(2, n+1): for j in range(10): if j == 0: dp[i][j] = dp[i-1][9] else: dp[i][j] = dp[i-1][9] - dp[i-1][j-1] + dp[i][j-1]print(dp[n][9] % 10007)풀이문제 분석오르막 수는 자릿수가..
https://www.acmicpc.net/problem/1890 처음 시간초과 코드- dfsn = int(input())board = []memo = [[0] * n for _ in range(n)]dx = [0, 1]dy = [1, 0]memo[0][0] = 1for i in range(n): board.append(list(map(int, input().split())))def move(dir, loc, memo): x, y = loc if x == n-1 and y == n-1: memo[n-1][n-1] += 1 return distance = board[x][y] nx = x + dx[dir] * distance ny = ..
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net dp[x][y] 를 (x, y)의 좌표에서의 최대 이동횟수라 했을 때 dp[x][y] = 1 + max(dp[x - 1][y], dp[x + 1][y], dp[x][y-1], dp[x][y+1] ) // 1+ max(상하좌우) 라고 할 수 있다, #include #include #include #include using namespace std; int N; int trees[500][..
https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 이 문제는 1 해당 칸에 대해 1번부터 다시 #include #include using namespace std; int N, r, c; int solve(int n, int cnt, int x, int y) { if (n == 1) { return cnt; } pair entry[4] = {{x, y}, {x, y + n / 2}, {x + n / 2, y}, {x + n / 2, y ..
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래의 좌표는 아래와 같다 (x, y), (x, y + n/2), (x + n/2, y), (x + n/2, y + n/2) #include #include #include using namespace std; int video[64][64]; vector ans; void printVideo(int n, int x, int y) { ans...
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net #include #include #include using namespace std; int n, c; vector vec; int binarySearch(int start, int end){ while(start = mid){ cnt += 1; cur = i; } } if(cnt < c) { end = mid - 1; }else{ start =..
