분류 전체보기82 [DP] 2225 - 합분해 (골드5) with Python https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 주저리 주저리 최근 dp관련 문제를 하두 풀다 보니, 문제를 보자마자 아 이건 dp겠네? 라는 생각이 먼저 들게 되었다. 문제 해결 일단 문제를 보면 0부터 N까지 정수 K개를 더해 그 합이 N이 되는 개수를 구하라... 게다가 1+2와 2+1은 서로 다른 것으로 판단한다라 그러면 더 쉽게 생각이 가능하다 판단하였다. 일단 dp[5][2]라고 해보자 (N=5, K=2) 즉 2개의 수로 더해 5을 만드는 경우의 수라고 생각하자 그러면 우린 dp[0][1] dp[1][1] dp[2][1] dp[3][1] dp[4][1] dp[.. 2023. 2. 18. [DP] 1309 - 동물원 (실버1) with Python https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 주저리 주저리 개인적으로 조금 시간이 많이 걸렸던 문제였다. 2 * n 타일링이 생각나는 그 문제 다른 점이라고 하면 사자는 서로 겹치지 않아야하고 아예 배치도 안 할수도 있다는 문제이다. 일단 문제를 보고 처음엔 규칙이 있나 확인해 보았지만 규칙이 보이지는 않았다. 즉 수열같은 규칙은 아니라는 말이고... 그럼 문제 자체를 들어가 봐야겠다. 문제 해결 저 가로 2칸 네모안에 왼쪽, 오른쪽 둘 중 하나에 배치를 할 수 있고, 배치도 안할수가 있다. 그렇게 생각해보면 위에서 배치를 안하는 케이스, 위에서 왼쪽에 배치를 한 케이스, .. 2023. 2. 18. [DFS] 1012 - 유기농 배추 (실버2) with Python https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 주저리 주저리 문제는 간단한 탐색 문제이다. 너비 탐색이던 깊이 탐색이던 문제가 없어서 깊이 탐색으로 진행하였다. 대표적인 dfs, bfs 문제로서 한번쯤 풀어보면 좋은 문제인것 같다. 문제 해결 import sys input = sys.stdin.readline T = int(input()) maps = [[False for _ in range(51)] for _ in range(51)] dx = [1,-1.. 2023. 2. 18. [DP] 9184 - 신나는 함수 실행 (실버2) with Python https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 주저리 주저리 문제에서 대놓고 시간이 오래 걸린다고 하고 있다. 재귀를 빠르게 끝내는 방법인 분할 정복 or dp 중에서 고르라는 것 같은데 문제를 보니 피보나치 처럼 이전 값을 메모라이징 하는 것이 옳다 판단해 dp로 작업을 시작하였다. 문제 풀이 일단 w함수를 수도코드에서 파이썬에 맞게 코드를 고쳐주었다. 그렇게 이제 dp를 만들고 메모라이징을 할려는 순간 a,b,c의 범위에 마이너스가 포함된 것.. 2023. 2. 18. 이전 1 ··· 15 16 17 18 19 20 21 다음 728x90
