본문 바로가기

dp33

[BOJ][Python]1149번 풀이 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net import sys ssr = sys.stdin.readline n = int(ssr()) cost = [list(map(int, ssr().split())) for _ in range(n)] min_cost = [[0,0,0] for _ in range(n)] min_cost[0] = cost[0] for i in range(1,n): min_cost[i][0] = min(.. 2022. 7. 26.

[BOJ][Python]11053번 풀이 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net n = int(input()) a = list(map(int, input().split())) dp = [1 for _ in range(n)] for i in range(n): for j in range(i+1,n): if a[j] > a[i]: dp[j] = max(dp[j], dp[i]+1) print(max(dp).. 2022. 7. 21.

[BOJ][Python]12928번 풀이 https://www.acmicpc.net/problem/12928 12928번: 트리와 경로의 길이 첫째 줄에 N과 S가 주어진다. (1 ≤ N ≤ 50, 1 ≤ S ≤ 1,000) www.acmicpc.net def sol(n,c):# n = 남은 노드 갯수, c = 현재까지 만들어진 2짜리 단일경로 갯수, 노드 2개짜리 트리에서 시작(2짜리 단일경로라 0개) if n == 0 and c == s:#모든 노드를 다 붙였을 때 단일 경로 갯수가 주어진 s와 같을 때 print(1)# 가능하다 exit()#프로세스 종료 if n == 0 or t[n][c] or c > s: #n이 0이거나 t[n][c]가 True거나, c가 s보다 클 때 return#리턴 t[n][c] = 1 for i in range.. 2022. 7. 19.

[BOJ][Python]2407번 풀이 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net n,m = map(int, input().split()) t = [0 for _ in range(101)] t[1] = 1 for i in range(2, 101): t[i] = i*t[i-1] print(t[n]//t[n-m]//t[m]) 아주 간단한 문제라 풀이가 필요없을지도 모르겠습니다만, 오랜만에 조합 공식도 떠올릴 겸 dp로 풀면 시간도 짧게 걸린다는 사실도 상기시킬 겸 작성해봤습니다. 큰 의미없이 포스팅 수만 늘어나는 일인지도 모르겠지만요. 2022. 7. 18.

[BOJ][Python]11727번 풀이 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net t = [0 for _ in range(1001)] t[1] = 1 t[2] = 3 for i in range(3,1001): t[i] = t[i-1] + 2*t[i-2] print(t[int(input())]%10007) 위 문제와 비슷한 문제는 이제 너무 많이 풀어봤죠? 몇 개 정도 손으로 써본 다음에 규칙만 찾으면 됩니다. 다만 그 규칙을 발견하는게 시간이 천차만별로 걸린다는 점이죠. 처음에 어떻게 될 것이다 하고 세운 .. 2022. 6. 26.

[BOJ][Python]19947번 풀이 https://www.acmicpc.net/problem/19947 19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net import math def sol(i): if i==11: return if i=3 and i 2022. 6. 13.

[BOJ][Python]11726번 풀이 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net t = [0 for _ in range(1001)] t[1],t[2],t[3] = 1,2,3 for i in range(4,1001): t[i] = t[i-1]+t[i-2] print(t[int(input())]%10007) 지난 번에 이거랑 똑같은 문제를 풀었던 것 같은 기분이 드는데요. 하도 dp 문제를 최근에 많이 풀어서 맞나 안맞나도 모르겠네요. dp문제는 몇 가지 경우를 써보다 보면 규칙이 보이기도 합니다. .. 2022. 6. 11.

[BOJ][Python]9461번 풀이 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net t = [0 for _ in range(101)] t[1],t[2] = 1,1 for i in range(3,101): t[i] = t[i-2]+t[i-3] n = int(input()) for _ in range(n): print(t[int(input())]) 늘 하던 dp 문제입니다. 피보나치와 동일하지만 약간 다른 점은 바로 이전의 수가 아닌 이전 2번째, 3번째 숫자의 합을 이용한다는 점일까요... 2022. 6. 10.

[BOJ][Python]2579번 풀이 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net n = int(input()) t = [0 for _ in range(301)] s = [0 for _ in range(301)] for i in range(1,n+1): s[i]=int(input()) t[1],t[2] = s[1],s[1]+s[2] for i in range(3,n+1): t[i] = max(s[i]+s[i-1]+t[i-3],s[i]+t[i-2]) print(t[n]) 저는 도저히 이걸 어.. 2022. 6. 9.

[BOJ][Python]10826번 풀이 https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net t = [0 for _ in range(10001)] t[1],t[2] = 1,1 for i in range(3,10001): t[i] = t[i-1]+t[i-2] print(t[int(input())]) 그냥 별 생각없이 랜덤돌렸는데 또 피보나치 문제가 나왔네요. 다만 이때까지 풀었던 것과 다른 것은 n이 0도 나온다는 점이네요. n범위가 좀 커서 굳이 큰.. 2022. 6. 8.

이전 1 2 3 4 다음

티스토리툴바