본문 바로가기

Algorithm/Dynamic Programming69

[파이썬] 백준 1577 : 도로의 개수 (골드5) [파이썬] 백준 1577 : 도로의 개수 (골드5) 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 문제 풀이 0. 방향성 생각 웰노운 문제 최단거리로 이동하니까 왼쪽위에서 시작해서 항상 아래, 오른쪽 방향으로만 간다. 왼쪽과 위쪽 테두리를 채워준 후, 어떤 지점의 왼쪽, 위쪽에서 들어오는 간선이 공사중이 아니면 값을 더해준다. 1. 입력 import sys input = lambda : sys.stdin.readline().rstrip() w,h = map(int,input().split().. 2023. 9. 29.
[파이썬] 백준 2758: 로또 (골드4) [파이썬] 백준 2758: 로또 (골드4) 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 문제 풀이 0. 방향성 생각 2차원 DP : dp[n번째 자리가][m으로 끝나는 경우의 수] 1. 전체 코드 dp = [[0]*2001 for _ in range(11)] dp[1] = [0]+[1]*2000 for n in range(1,10): for x in range(2001): if x//2: dp[n+1][x] += sum(dp[n][:x//2+1]) for _ in range(int(input())): n,m = m.. 2023. 9. 25.
[파이썬] 백준 2602 : 돌다리 건너기 (골드4) [파이썬] 백준 2602 : 돌다리 건너기 (골드4) 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 문제 풀이 0. 방향성 생각 DP n가지 상태 -> n+1가지 상태 존재 dp[밟은 개수][선택한 다리][발판 번호] = 경로 개수 저장 dp[다음 상태][선택한 다리][발판 번호] += dp[이전 상태][반대편 다리][이전 발판] (반대편 다리 검사, 현재 발판번호보다 작고 이전 상태에 해당하는 문자일 경우) 1. 입력 import sys input = lambda: sys.stdin.readline().rstrip(.. 2023. 9. 13.
[파이썬] 백준 20303: 할로윈의 양아치 (골드3) [파이썬] 백준 20303: 할로윈의 양아치 (골드3) 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 문제 풀이 0. 방향성 생각 BFS로 군집 크기, 사탕 수 계산 DP로 최대값 구하기 1. 입력 from collections import deque import sys input = lambda : sys.stdin.readline().rstrip() n,r,limit = map(int,input().split()) can.. 2023. 9. 7.

티스토리툴바