무니화니

저번에 포스팅한 N과 M (1)에 유사한 문제입니다. 풀이: 이 문제에서 제일 중요한 포인트는 DFS를 이용한 풀이법보다도, 밑에서 리스트 내에 리스트가 있는 경우에 어떻게 대응해야하는지입니다. 밑에 answer라는 list에는 중복이 존재하는 list가 있습니다. 이럴 때, 바로 set에 넣기에는 list라는 자료형을 넣을 수 없습니다. 그렇기에, tuple로 한번 옮겨주고, set에 넣으면 되겠습니다.

오랜만에 포스팅해봅니다! 휴가 및 격리 때문에 그동안 공부를 하지 못했네요 ㅠ 아직 백트래킹에 대한 내용을 아는 게 없었기에 각종 블로그 및 풀이들을 보고 결정했다. 물론 combination을 외부 라이브러리에서 사용할 수 있었지만, 이는 별로 교육적으로 도움이 되지 않을 것 같아서 이 방법은 사용하지 않았다. 내 풀이: 여기서 사용되는 d는 depth의 줄임말로, 몇 개의 수를 출력해야 하는 지를 담고 있다. solved라는 함수를 만들어서, 전 depth로 넘어가기 전에 result에 쓰이지 않는 수를 넣는 식으로 함수를 완성했다.

오늘의 문제! 카잉 달력이다. 문제를 보자마자, 저번에 풀었던 문제 (https://www.acmicpc.net/problem/1476)와 굉장히 비슷하다고 느꼈다. 하지만, 절대 같지 않았다. 우선 오답코드부터 보자. n=int(input()) for i in range(n): n,m,ansX,ansY=map(int,input().split()) x=1 y=1 year=1 while True: if x==ansX and y==ansY: print(year) break if x==n and y==m: print(-1) break if x==n: x=1 else: x+=1 if y==m: y=1 else: y+=1 year+=1 이렇게 단순하게 하나하나 더하면서 구하면, 시간 초과가 뜨게 된다. 아쉽다....

이제 지겨운 DP를 끝내고, 더욱 재밌어보이는(?) 브루트포스를 풀고 있다. 근데 어렵다...... 특히 구현하는 문제가 난이도가 높아보인다. 진짜 역대급이다. 왜이렇게 배열을 떠올리면서 문제를 푸는 것이 어려운지.... 다른 사람들의 코드를 보고 정리해서 써봤다. def check(arr): n=len(arr) answer=1 for i in range(n): count=1 for j in range(1,n): if arr[i][j]==arr[i][j-1]: count+=1 else: count=1 if count>answer: answer=count count=1 for j in range(1,n): if arr[j][i]==arr[j-1][i]: count+=1 else: count=1 if cou..

다이내믹 프로그래밍 문제는 정말 많다....ㅠ 문제가 많은 만큼, 만들어 낼 수 있는 점화식도 정말 다양하고, 문제의 종류도 정말 많다. 그런 만큼, 더욱 열심히 문제를 풀어야겠다는 생각이 든다. n=int(input()) data=[] for i in range(n): data.append(list(map(int,input().split()))) dp=data dp[0]=data[0] for i in range(1,n): for j in range(i+1): if j==0: dp[i][0]=dp[i-1][0]+data[i][0] elif i==j: dp[i][j]=dp[i-1][j-1]+data[i][j] else: dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+data[i][j]..

오늘도 계속되는 dynamic programming! n=int(input()) data=[] for i in range(n): data.append(int(input())) dp=[0]*n dp[0]=data[0] if n>1: dp[1]=data[0]+data[1] if n>2: dp[2]=max(data[0]+data[2], data[1]+data[2], data[0]+data[1]) for i in range(3,n): dp[i]=max(dp[i-2]+data[i],dp[i-3]+data[i-1]+data[i],dp[i-1]) print(dp[n-1]) 이 문제에서는, 3번 연속으로 와인을 마시면 안된다. 그렇기에, 3개 이상의 와인이 시식 가능할 때, i-3 i-2 i-1 i i-3 i-2 i-..

하... 이 문제를 보고 참아버리지 못했다. 물론 지금 컴퓨터 공부를 하고 있지만, 수학적으로 문제를 봐버리고 나니 다른 해답으로 풀기가 싫어진다. 문제부터 보자. 이 문제를 보고 dynamic programming으로 풀까라는 생각이 1초정도 났지만, 바로 확률과 통계에서 나오는 중복조합 H가 생각났다. 딱 중복 가능한, 순서 따져야 하는.... 중복조합 아닌가! 이걸로 풀었다. import math n=int(input()) print((math.factorial(9+n)//(math.factorial(9)*math.factorial(n)))%10007) 하지만, 코더의 본분은 코딩이거늘... dp로 마지막 자리로 index 잡고, 하나씩 늘려주면 된다! 하하 수학 1승.!

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 오늘의 문제다! 우선 실패한 코드부터 올려보려고 한다. n=int(input()) data=list(map(int,input().split())) streak=[1]*n pastScore=data for i in range(n): for j in range(0,i): if data[i] > pastScore[j]: st..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 오늘의 문제다! 우선 실패한 코드부터 올려보려고 한다. n=int(input()) data=list(map(int,input().split())) streak=[1]*n pastScore=data for i in range(n): for j in range(0,i): if data[i] > pastScore[j]: st..

안녕하세요! 23살 무니화니로 찾아뵙습니다! 새해 복 많이 받으시고 항상 즐코딩하십쇼! https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 이 문제를 읽자마자, 굉장히 복잡하겠다는 생각이 들었다. 사실 근데 문제만 요란하지, 푸는 문제는 다이내믹 프로그래밍 그 자체로 풀 수 있었다. n=int(input()) cards=[0]+list(map(int,input().split())) prices=[0]*(n+1) for i in range(1,n+1): f..