분류 전체보기 (402) 썸네일형 리스트형 [백준 3176번] 도로 네트워크 (Python3) import sys input = sys.stdin.readline from collections import deque from math import log2 def findparent(x,d): global minresult,maxresult for i in range(logd+1): if d&(1 depth[x]: y = findparent(y,depth[y]-depth[x]) if x != y: c = int(log2(depth[x]-1)) findcoparent(x,y,c) print(minresult,maxresult) LCA2 [백준 11438번] LCA 2 (Python3) (tistory.com) 를 활용하는 문제. LCA2를 풀었다면 풀이는 금방 떠올릴 수 있지만 구현하는게 약간 까다로.. [백준 11438번] LCA 2 (Python3) import sys input = sys.stdin.readline from collections import deque from math import log2 def findparent(x,d): for i in range(logd+1): if d&(1 [백준 2494번] 숫자 맞추기 (Python3) N = int(input()) data1 = [*map(int,input())] data2 = [*map(int,input())] DP = [[0]*10 for i in range(N+1)] path = [[0]*10 for i in range(N+1)] for n in range(N): n = N-1-n for i in range(10): d = (data2[n]-data1[n]-i)%10 l,r = d+DP[n+1][(d+i)%10],10-d+DP[n+1][i] if l0: i = (c+i)%10 방법을 출력하지 않는 숫자 맞추기 [백준 13392번] 방법을 출력하지 않는 숫자 맞추기 (Python3) (tistory.com) 에서 방법을 출력하는 문제이다. 풀이과정은 그냥 똑같고, 경로에 대한 배열.. [백준 13392번] 방법을 출력하지 않는 숫자 맞추기 (Python3) N = int(input()) d1 = [*map(int,input())] d2 = [*map(int,input())] DP = [[0]*10 for i in range(N+1)] for n in range(N): n = N-1-n for i in range(10): d = (d2[n]-d1[n]-i)%10 DP[n][i] = min(d+DP[n+1][(d+i)%10],10-d+DP[n+1][i]) print(DP[0][0]) 재미있는 DP 문제였다. 아이디어를 떠올리기가 생각보다 쉽지 않았다. 핵심은 경우의 수를 10가지로 축약하는 것이다. n번째 숫자를 돌린다고 가정하자. 이때 0~n-1번째 숫자들을 왼쪽으로 돌린 횟수의 총 합을 X번이라고 하자. 그러면 현재 위치의 숫자는 (원래숫자 + X)를 10.. [백준 1311번] 할 일 정하기 1 (Python3) import sys input = sys.stdin.readline INF = 10**6 def DFS(n,bit): if n == N: DP[n][bit] = 0 return for i in range(N): if bit&(1 [백준 2169번] 로봇 조종하기 (Python3) import sys input = sys.stdin.readline INF = 10**9 N,M = map(int,input().split()) mars = [] for i in range(N): mars.append([*map(int,input().split())]) DP = [[[-INF]*(M+2) for i in range(N+1)] for i in range(2)] DP[0][0][1] = 0 for y in range(1,N+1): for x in range(1,M+1): DP[0][y][x] = max(max(DP[0][y-1][x],DP[1][y-1][x]),DP[0][y][x-1])+mars[y-1][x-1] x = M+1-x DP[1][y][x] = max(max(DP[0][y-1][x.. [백준 1517번] 버블 소트 (Python3) import sys input = sys.stdin.readline def updateseg(a,start,end,x): if a == end: seg[x] += 1 return mid = (start+end)//2 if a [백준 16975번] 수열과 쿼리 21 (Python3) import sys input = sys.stdin.readline def updateseg(k,a,b,start,end,x): if a==start and b==end: seg[x] += k return mid = (start+end)//2 if b mid: updateseg(k,a,b,mid+1,end,x*2+1) else: updateseg(k,a,mid,start,mid,x*2) updateseg(k,mid+1,b,mid+1,end,x*2+1) def sumseg(n,start,end,x): global SUM SUM += seg[x] if start==end: return mid = (start+end)//2 if n 이전 1 ··· 26 27 28 29 30 31 32 ··· 51 다음 목록 더보기
