본문 바로가기

분류 전체보기

 (402)
[백준 17401번] 일하는 세포 (Python3) import sys,copy input = sys.stdin.readline sys.setrecursionlimit(10**6) mod = 1000000007 def multiply(A,B): matrix = [[0]*N for i in range(N)] for i in range(N): for j in range(N): for k in range(N): matrix[i][j] += A[i][k]*B[k][j] matrix[i][j] %= mod return matrix def cal(A,n): if not n: return I if n == 1: return A cal2 = cal(A,n//2) if not n%2: return multiply(cal2,cal2) return multiply(multi..
[백준 18122번] 색깔 하노이 탑 (Python3) N = int(input()) hanoi = [0] for i in range(N-1): hanoi.append((hanoi[-1]*2+1)%1000000007) print((3+hanoi[-1]*8)%1000000007) DP로 해결하였다. 일반 하노이탑과의 차이점을 생각하면 쉽게 해결할 수 있다. 가장 큰 블록을 순서대로 옮기기 위해서는 3번의 움직임이 필요하다. 이때 가장 큰 블록을 옮길 때마다 일반 하노이탑을 옮기듯이 나머지 하노이탑을 옮겨야하고, 가장 큰 블록을 다 옮기고 나서 나머지 하노이탑을 옮겨야 하므로 가장 큰 블록을 제외한 나머지 블록은 총 4번 옮긴다. 이때 4번 옮기면 짝수번 옮기는 셈이므로 순서는 변하지 않아 따로 조정할 필요가 없다. 모든 블록이 2개씩 있으므로, 가장 큰 블록을..
[백준 14942번] 개미 (Python3) import sys,collections,math input = sys.stdin.readline def climb(x,e,c): if not c: if cost[0][x]
[백준 1086번] 박성원 (Python3) import sys,math input = sys.stdin.readline def DFS(k,bit,l): DP[k][bit] = 0 if bit == (1
[백준 3948번] 홍준이의 친위대 (Python3) for i in range(int(input())): print([1,2,4,10,32,122,544,2770,15872,101042,707584,5405530,44736512,398721962,3807514624,38783024290,419730685952,4809759350882,58177770225664,740742376475050][int(input())-1]) 지그재그 서기 [백준 1146번] 지그재그 서기 (Python3) (tistory.com) 와 똑같은 문제에서 테스트케이스 수가 늘었고, N의 크기가 매우 작아졌다. 따라서 그냥 지그재그 서기의 알고리즘으로 1~20까지의 값을 구한 뒤, 출력해주었다.
[백준 1146번] 지그재그 서기 (Python3) def DFS(n,now): if not (N-n)%2: for next in range(now,n): if not DP[n-1][next]: DFS(n-1,next) DP[n][now] += DP[n-1][next] else: for next in range(now): if not DP[n-1][next]: DFS(n-1,next) DP[n][now] += DP[n-1][next] DP[n][now] %= 10**6 N = int(input()) if N==1: print(1) else: DP = [[1]]+[[0]*N for i in range(N)] DFS(N,0) print(2*DP[N][0]%10**6) 간단한 DP 문제 DP를 어떻게 설정할지가 가장 중요하며, 구현은 매우 쉽다. 알고리즘을 설..
[백준 3163번] 떨어지는 개미 (Python3) import sys,collections input = sys.stdin.readline for _ in range(int(input())): N,L,k = map(int,input().split()) location,id = [],collections.deque() fall = [] for _ in range(N): l,i = map(int,input().split()) location.append(l) id.append(i) if i < 0: fall.append((location.pop(),id.popleft())) while location: fall.append((L-location.pop(),id.pop())) print(sorted(fall)[k-1][1]) 스택을 이용해서 해결하였다. 아이..
[백준 1648번] 격자판 채우기 (Python3) def makebit(bit): if len(bit) > N: return if len(bit) == N: bitlist.add(int(bit,2)) return makebit(bit+"00") makebit(bit+"1") def DFS(m,bit): if m == M-1: DP[m][bit] = int(bit in bitlist) return DP[m][bit] = 0 for bit1 in bitlist: if bit1|bit != bit1: continue if DP[m+1][bit1-bit] == -1: DFS(m+1,bit1-bit) DP[m][bit] += DP[m+1][bit1-bit] DP[m][bit] %= 9901 N,M = map(int,input().split()) bitlist =..

티스토리툴바