본문 바로가기

공부/알고리즘42

[알고리즘][백준] 16194번 카드 구매하기 2 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 11502번 카드 구매하기 번외 문제다! 지난주에 돈을 많이 써서 이번에는 최소금액을 구해야한다ㅋㅋ import sys n = int(sys.stdin.readline()) p = [0] + list(map(int, sys.stdin.readline().split())) dp = [0] * 1001 for i in range(1, n+1): for j in range(1, i+1): if dp[i] .. 2024. 3. 5.
[알고리즘][백준] 9095번 1, 2, 3 더하기 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 무슨 규칙이 있나 살펴보니 1 = 1 2 = 2 3 = 4 4 = 7 = 1 + 2 + 4 5 = 13 = 2 + 4 + 7 앞의 세수를 더하면 값이 나온다! 5의 경우 4에서 1더하기 3에서 2더하기 2에서 3더하기 3가지 종류가 있기 때문에 위와 같이 나오게 된다. 코드는 아래와 같다! import sys t = int(sys.stdin.readline()) dp = [0] * 11 dp[1] = 1 dp[2] = 2 dp[3] = 4 for _ in range(t): n = int(sys... 2024. 3. 5.
[알고리즘][백준] 17103번 골드바흐 파티션 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 1 = 1 2 = 3 3 = 5 = 2*1 + 3 4 = 11 = 2*3 + 5 5 = 21 = 2*5 + 11 8 = 171 12 = 2731 직접 그려보면서 위와 같은 규칙을 발견했다 import sys n = int(sys.stdin.readline()) dp = [0] * 1001 dp[1] = 1 dp[2] = 3 for i in range(3, n+1): dp[i] = dp[i-1] + 2*dp[i-2] print(.. 2024. 3. 5.
[알고리즘][백준] 11726번 2×n 타일링 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 타일 개수를 구해보면 결국 피보나치 수열을 구하는 문제이다 import sys n = int(sys.stdin.readline()) dp = [0] * (n+1) dp[1] = 1 dp[2] = 2 ''' 1 = 1 2 = 2 3 = 3 4 = 5 5 = 8 ''' for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n] % 10007) 이렇게 하니 런타임에러가 발.. 2024. 3. 5.

티스토리툴바