본문 바로가기

분류 전체보기

(402)
[백준 19238번] 스타트 택시 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,-1,0,0] dx = [0,0,1,-1] def BFS(): cnt = 0 fuel = K start = first while True: if cnt == M: print(fuel) return visited = [[0]*N for i in range(N)] dq = deque() dq.append((*start,0)) distance = 1000 passenger = M+2 while dq: y,x,d = dq.popleft() if d>distance: break if d > fuel: print(-1) return if visited[y][x]: continue ..
[백준 1029번] 그림 교환 (Python3) import sys input = sys.stdin.readline def DFS(cost,now,bit): if DP[cost][now][bit]: return for next in range(N): if bit&(1
[백준 13976번] 타일 채우기 2 (Python3) import sys input = sys.stdin.readline mod = 1000000007 def multiply(A1,A2): result = [[0,0],[0,0]] for i in range(2): for j in range(2): for k in range(2): result[i][j] += A1[i][k]*A2[k][j] result[i][j] %= mod return result def cal(A,n): if n == 1: return A cal2 = cal(A,n//2) result = multiply(cal2,cal2) if n%2: return multiply(result,A) return result N = int(input()) if N%2: print(0) else: N //..
[백준 2133번] 타일 채우기 (Python3) import sys input = sys.stdin.readline from math import factorial def DFS(SUM,last): global result if SUM == N: x = factorial(sum(cntlist)) x //= factorial(cntlist[1]) x *= 3**cntlist[1] for i in range(2,N+1): x *= 2**cntlist[i] x //= factorial(cntlist[i]) result += x if SUM > N: return for i in range(last,N+1): cntlist[i] += 1 DFS(SUM+i,i) cntlist[i] -= 1 N = int(input()) if N%2: print(0) else: ..
[백준 15730번] 수영장 사장님 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,-1,0,0] dx = [0,0,1,-1] def BFS(): visited = [[0]*(M+2) for i in range(N+2)] dqlist[0].append((0,0)) for n in range(10001): while dqlist[n]: y,x = dqlist[n].popleft() if visited[y][x]: continue visited[y][x] = 1 waterlevel[y][x] = n for i in range(4): y1,x1 = y+dy[i],x+dx[i] if N+2>y1>=0 and M+2>x1>=0: if visited[y1][x1]..
[백준 3197번] 백조의 호수 (Python3) 구현문제는 시간만 오래걸리지 쉽다는 편견을 깬 문제였다. 지금까지의 구현문제는 알고리즘만 떠올리면 시간초과는 신경쓸 필요가 거의 없었는데, 시간초과를 해결하기 위한 트릭? 테크닉?이 요구됐다. 처음에 제출한 코드는 이러하다. import sys input = sys.stdin.readline from collections import deque dy = [1,-1,0,0] dx = [0,0,1,-1] N,M = map(int,input().split()) lake = [] for i in range(N): lake.append([*map(lambda x:-1 if x=="X" else 0 if x=="." else 1,input().strip())]) swan = [] dq = deque() for y ..
[백준 1039번] 교환 (Python3) 처음에는 너무 쉬운 그리디 알고리즘 문제라고 생각하였다. 가장 첫째자리부터 현재 자리에서 그 다음 자리의 숫자들 중 현재 자리의 숫자보다 큰 수가 존재하면 가장 큰 수와 위치를 바꿔주면 된다고 생각하였다. 코드는 다음과 같다. import sys input = sys.stdin.readline def change(): same = False for i in range(L-1): x = numlist[i] y = -1 yi = -1 for j in range(i+1,L): if numlist[j] >= y: yi = j y = numlist[j] if y > x: numlist[i] = y numlist[yi] = x return elif y == x: same == True if same: return ..
[백준 1113번] 수영장 만들기 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,-1,0,0] dx = [0,0,1,-1] def BFS(y,x,n): visited = [[0]*M for i in range(N)] dq = deque() dq.append((y,x)) co = [] border = [] while dq: y,x = dq.popleft() if visited[y][x]: continue visited[y][x] = 1 if pool[y][x] >= n: border.append((y,x)) continue co.append((y,x)) for i in range(4): y1,x1 = y+dy[i],x+dx[i] if not (N>y1..