본문 바로가기

백준 알고리즘108

파이썬) 백준 알고리즘 | 9661번 : 돌 게임 7 https://www.acmicpc.net/problem/9661 9661번: 돌 게임 7 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 풀이 https://ddo-code.tistory.com/127 파이썬) 백준 알고리즘 | 9660번 : 돌 게임 6 https://www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 풀이 처음에 dp로 접근하였지만 메모리 초과가 떠서 stack으로 구현하였었다... ddo-code.tistory.com 이 블로그를 참고하길 바란다. n = int(input()) if n == 2:.. 2022. 6. 30.
파이썬) 백준 알고리즘 | 9660번 : 돌 게임 6 https://www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 풀이 처음에 dp로 접근하였지만 메모리 초과가 떠서 stack으로 구현하였었다. n = 1일 때는 선공이 이기고 n = 2일 때는 후공이 이기게 된다 n = 3일 때는 1,1,1 또는 3 을 가져가게 되어 선공이 이기고 n = 4일 때는 4개를 가져갈 수 있어서 선공이 이기게 된다. n = 5일 때는 1, 3, 4개를 가져갈 수 있으므로 n=4, n=2, n=1의 경우중에 후공이 이기는 경우가 1개 이상만 있으면 선공이 이기게 된다. 예를 들어 n = 5일 때 1을 가져가면 후공이 n = 4일 때 선공을 잡는 .. 2022. 6. 30.
파이썬) 백준 알고리즘 | 1699번 : 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net pseudo code dp 배열을 만든다 dp[i]에는 dp[i-1]과 dp[i-n^2]들을 비교해서 최솟값을 할당한다 dp[-1]을 출력한다 import math n = int(input()) dp = [0] * (n+1) for i in range(1, n+1): a = math.floor(i**0.5) dp[i] = min(dp[i-1]+1, dp[i-.. 2022. 6. 30.
파이썬) 백준 알고리즘 | 1912번 : 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp를 이용하면 쉽게 풀 수 있는 문제입니다. 연속되는 수열의 최대 합이기 때문에 처음부터 더하다가 중간에 큰 수가 나오면 이전까지 더한 것을 버리면 됩니다. n = int(input()) seq = list(map(int, input().split(' '))) dp = seq for i in range(1, n): dp[i] = max(dp[i-1]+dp[i], dp[i]) print(max(dp)) 2022. 6. 30.

티스토리툴바