Algorithm/Dynamic Programming69 [파이썬] 백준 18244 : 변형 계단 수 (골드3) [파이썬] 백준 18244 : 변형 계단 수 (골드3) 18244번: 변형 계단 수 첫째 줄에 정답을 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 0. 방향성 생각 상태가 5개로 나뉜다. 시작 상태 : 증감 구분이 안돼있음 1개 연속 증가 : 시작상태에서 오거나 감소상태에서 오는경우 2개 연속 증가 : 1개 연속 증가에서 또 증가 1개 연속 감소 : 시작상태에서 오거나 증가상태에서 오는경우 2개 연속 감소 : 2개 연속 감소에서 또 감소 1. 입력 n = int(input()) dp = [[[0]*10 for _ in range(n)] for _ in range(5)] dp[0][0] = [1]*10 k = 10**9+7 # dp[state][stage][.. 2023. 11. 23. [파이썬] 백준 1636 : 한번 열면 멈출 수 없어 (골드4) [파이썬] 백준 1636 : 한번 열면 멈출 수 없어 (골드4) 1636번: 한번 열면 멈출 수 없어 첫째 줄에 프링글스 맛의 개수 N이 주어진다. N은 1이상 100,000이하인 정수이다. 그 다음 줄부터 N줄에 걸쳐 두 개의 정수 si, ei (1 ≤ si ≤ ei ≤ 200)가 주어지는데, i번째 프링글스 맛의 중독스트레 www.acmicpc.net 문제 풀이 0. 방향성 생각 DP. 입력이 10만이라 10**6 *201 사이즈로 만드는건 힘들다. 각 프링글스 범위에 맞는 사이즈로 넣어준다. 1. 입력 n = int(input()) inf = 1e9 info,dp,trace = [],[],[] for i in range(n): a,b = map(int,input().split()) info.appe.. 2023. 11. 5. [파이썬] 백준 14550 : 마리오 파티 (골드5) [파이썬] 백준 14550 : 마리오 파티 (골드5) 14550번: 마리오 파티 입력은 20개 이하의 테스트케이스로 구성되어 있고, 맨 끝에 0이 온다. 각 테스트케이스의 첫 줄에는 N (출발점과 별 사이의 칸 수), S, T가 주어진다. 2 ≤ N ≤ 200, 2 ≤ S ≤ 10, N + 1 ≤ ST, T ≤ N + 1이 www.acmicpc.net 문제 풀이 0. 방향성 생각 순방향 DP 최대값을 구하고 값이 arr가 음수인 부분이 있으므로 DP 초기화를 -1e9로 시켜준다 1. 입력 while True: info = list(map(int,input().split())) if info == [0]: break n,dice,chance = info arr = [] while len(arr) < n: .. 2023. 10. 22. [파이썬] 백준 2193 : 이친수 (실버3) [파이썬] 백준 2193 : 이친수 (실버3) 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 방향성 생각 2가지 상태가 나누어진 DP 현재 1인경우 다음은 0 현재 0인경우 다음은 0 또는 1 전체코드 n = int(input()) dp = [[0]*n for _ in range(2)] dp[1][0] = 1 for i in range(n-1): dp[0][i+1] += (dp[0][i] + dp[1][i]) dp[1][i+1] += dp[0][i] print(dp[0][-1]+dp[1.. 2023. 10. 12. 이전 1 ··· 8 9 10 11 12 13 14 ··· 18 다음
