알고리즘29 [DP] 1904 - 01타일 (실버3) with Python https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 주저리 주저리 dp를 하두 풀어보니 이제 이런 문제는 보자마자 답이 나오기 시작한다... 나는 dp에 약했었는데(그래프랑 dp랑...그리디랑...) 집중적으로 파기 시작하니 사람이 꼭 죽으라는 법은 없는 것 같다 하지만 그래봤자 아직 골5 ~ 실버문제들... 못해도 골드 2~3까지는 가는것이 목표이다. 아자! 문제 해결 문제 해결방법은 간단한 규칙만 생각하면된다 n번째에서 둘수 있는 방법은 전단계의 영.. 2023. 2. 18. [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. 이전 1 ··· 3 4 5 6 7 8 다음 728x90
