본문 바로가기
반응형

백준224

[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]9375번 풀이 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net t = int(input()) for _ in range(t): n = int(input()) cl = [input().split() for _ in range(n)] c = {i[1]:[] for i in cl} ans_l = [] for i in cl: c[i[1]].append(i[0]) for i .. 2022. 6. 9.
[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.
[BOJ][Python]17626번 풀이 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net import math t = [0 for _ in range(50001)] t[0],t[1],t[2],t[3]=0,1,2,3 for i in range(4,50001): minv=5 a = math.floor(math.sqrt(i)) for j in range(1,a+1): minv = min(minv, t[i-j**2]+1) t[i] = minv print(t.. 2022. 6. 7.
[BOJ][Python]1535번 풀이 https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net n = int(input()) p = [0] h = [0] p.extend(list(map(int, input().split()))) h.extend(list(map(int, input().split()))) t = [[0 for _ in range(101)] for _ in range(n+1)] for i in range(1,n+1): for j in range(101): if j 2022. 6. 6.
[BOJ][Python]11399번 풀이 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net n = int(input()) p = list(map(int, input().split())) p.sort() ans = 0 for i in range(n): ans += p[i]*(n-i) print(ans) 간단한 문제입니다. 설명도 자세하게 적어줘서 어떻게 접근할지 금방 떠올랐어요. 앞에서 걸렸던 시간이 뒤에서도 계속 해서 반복적으로 걸리기 때문에 최소 시간을 구하기 위해서는 시간이 오래 걸리는 경우일수록 뒤에 있으면 된.. 2022. 6. 6.
[BOJ][Python]12865번 풀이 길었던 대장정의 끝입니다. 정말 오랫동안 고민했던 문제입니다만 결국 온전히 제 힘만으로는 풀어내지 못했네요. 배낭 문제는 많으니까 다음에 다른 문제를 혼자서 풀어서 설욕을 해야겠어요. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net import sys ssr = sys.stdin.readline n,k = map(int, ssr().split()) t = [[0 for _ in .. 2022. 6. 5.
[BOJ][Python]14606번 풀이 https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net import math n = int(input()) t = [0 for _ in range(n+1)] t[1] = 0 for i in range(2,n+1): t[i] = math.ceil(i/2)*(i-math.ceil(i/2)) + t[math.ceil(i/2)] + t[i-math.ceil(i/2)] print(t[n]) 처음엔 이게 왜 dp인가 싶었는데 식을 구하려고 그림을 그.. 2022. 6. 5.
반응형

티스토리툴바