본문 바로가기

분류 전체보기142

파이썬) 백준 알고리즘 | 20004번 : 베스킨라빈스 31 https://www.acmicpc.net/problem/20004 20004번: 베스킨라빈스 31 베스킨라빈스 게임은 1부터 31까지의 수를 순차적으로 한번에 1개 이상, 3개 이하 연달아 부를 수 있으며, 마지막 31을 부른 사람이 지는 게임이다. 시온이와 민우는 베스킨라빈스 게임을 하기로 www.acmicpc.net 풀이 부를 수 있는 숫자가 2인 경우에서 31이 아니라 지정한 수라고 생각하면 필승하는 사람은 1 -> 후공 2 -> 선공 3 -> 선공 4 -> 후공 이런식으로 전개가 된다. 부를 수 있는 숫자가 n일 경우에는 1 -> 후공 ... 2~ n+1 -> 선공 n+2 -> 후공 ... 이런식으로 전개가 된다. 31 에서 내가 선일 경우 31-n 중에 후공이 필승하는 전략을 쓰면 이기게 된다.. 2022. 7. 1.
파이썬) 백준 알고리즘 | 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.

티스토리툴바