목록다이나믹 프로그래밍 (8)

동캄의 코딩도장

백준 5525 [IOIOI] 파이썬

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net #백준 5525 IOIOI import sys input=sys.stdin.readline N=int(input()) M=int(input()) S=list(map(str,input().rstrip())) target=2*N+1 dp=[0]*(M) answer=0 if S[0]=='I': dp[0]=1 for i in range(..
코테/BOJ 2023. 3. 21. 10:30
백준 4811 [알약] 파이썬

https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net # 백준 4811 알약 import sys input = sys.stdin.readline ans = [0]*(32) dp = [[0]*32 for _ in range(32)] for i in range(1, 32): dp[i][0] = 1 for i in range(1, 32): for j in range(1, i+1): dp[j][i] = dp[j-1][i]+dp[j][i-1] # dp[j+1][i]=dp[j..
코테/BOJ 2022. 9. 19. 17:04
백준 9507 [Generations of Tribbles] 파이썬

https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net #백준 9507 import sys n=int(sys.stdin.readline()) dp=[1,1,2,4] for i in range(4,70): dp.append(dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4]) for _ in range(n): k=int(sys.stdin.readline()) print(dp[k]) dp 문제이다.
코테/BOJ 2022. 9. 5. 17:57
백준 2407 [조합] 파이썬

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net #백준 2407 import sys n,k=map(int,sys.stdin.readline().split()) dp=[1]*(n+1) for i in range(2,n+1): dp[i]=dp[i-1]*i print(dp[n]//(dp[n-k]*dp[k])) 수학과 dp를 절묘히 조화시키면 풀 수 있는 문제이다.
코테/BOJ 2022. 9. 5. 17:56
백준 1904 [01 타일] 파이썬

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net #백준 1904 import sys n=int(sys.stdin.readline()) dp=[0]*(1000001) dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=(dp[i-1]+dp[i-2])%15746 print(dp[n]) dp 문제이다.
코테/BOJ 2022. 9. 5. 17:55
백준 9461 [파도반 수열] 파이썬

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net #백준 9461 import sys T=int(sys.stdin.readline()) dp=[0,1,1,1] for i in range(4,101): dp.append(dp[i-2]+dp[i-3]) for i in range(T): n=int(sys.stdin.readline()) print(dp[n]) dp를 이용하는 문제이다.
코테/BOJ 2022. 9. 5. 17:50
이전 Prev 1 2 Next 다음