10164 격자상의 경로 [python] k 포인트 기준으로 두개의 영역으로 나눠 그 경우의수를 곱하는 방식을 이용하였다. 메모제이션을 사용하지않고 완전탐색을 하면 15x15 크기여도 시간초과로 인해 풀 수가 없다. 각 이동경로마다 방문된 곳이면 방문하지않고 방문된곳의 크기를 올리는 방식으로 문제를 풀었다 방문하는방법은 bfs를 이용하였다. def bfs(sy, sx, ey, ex): direct = [[0, 1], [1, 0]] q = [(sy, sx)] matrix[sy][sx] = 1 while q: y, x = q.pop(0) for dy, dx in direct: cy = dy + y cx = dx + x if cy >= ey + 1 or cx >= ex + 1: continue if matrix[cy][cx]: matrix[cy][c.. 더보기 2512 예산 [Python] 이진탐색을 이용하면 시간안에 풀 수 있다. def binary_search(): first, last = 0, max(arr) check = 0 while first x: check = 0 mid = (first + last) // 2 for i in arr: if i < mid: check += i else: check += mid if check 더보기 1937 욕심쟁이 판다 [Python] 문제대로 2차원 배열을 이용한 맵을 만든후 1,1 위치부터 판다가 살수 있는 최대일수를 구하는 방식으로 구현했다. 최대일수 구하는 방법은 dfs를 이용하였으며 재귀를 통해 방문될때마다 그 재귀를 호출한 스택에는 +1값을 주도록 하였다 최대일수가 메모되있으면 다른 행열을 찾아보는방식으로 시간을 절약하였다. import sys sys.setrecursionlimit(10**6) read = sys.stdin.readline def dfs(y, x): cache[y][x] += 1 for dy, dx in direct: cy = dy + y cx = dx + x if cy = n or cx >= n: continue if matrix[y][x] < matrix[cy][cx.. 더보기 이전 1 ··· 7 8 9 10 11 12 13 ··· 22 다음