CS

타일 싫어... 진짜 엄청 고민했던 문제. 겹치는 경우가 많아서 겹치지 않는 경우로 세야한다. n=3인 경우, 여기서 잘보면 두가지로 분류 할 수 있는데, 처음에 2*1이 온 경우와, 처음에 2*2또는 1*2가 온 경우이다. 처음에 2*1이 온 경우, n=3이므로 1을 뺀, n(2)와 같은 값을 가진다. 처음에 2*2나 1*2가 온 경우, n=3이므로, 2만큼 뺀, n(1)만큼의 값을 가진다. 따라서 일반항은 n(k)=n(k-1)+2*n(k-1)이다. 다시한번 살펴보면, 빨간 박스(2*2)는 처음 세는 값이므로 여기에는 이전 값의 모든 값이 와도 된다. 하지만 두번째, 파란박스에는 ㅣㅣ(2*1 2개)가 오면 빨간 박스와 겹치는 경우가 생긴다. 그래서 파란 박스에 올 수 있는 경우 중 2*2와 1*2 두개..

개인적으로 굉장히 어려웠던 문제... 첫째로, 최대 수도관 용량으로 dp를 할지, 길이로 dp로 할지 정한다고 해맸다. 두번째로, 입력받아서 배열에서 꺼내쓰려다가 시간초과로 쳐맞았다. 세번째로, 중복사용때문에 고생했다. 아무튼 코드는 아래와 같다. 초기화 방법은 입력값이 1이라고 하면 dp[1]이 들어가는 모든 값의 합을 바꾼다. x가 7이라고 한다면, dp[7]=min(1,dp[7-1])이다. 그리고 만약 dp[7]이 입력이 들어오면 변경 해주는 방식이다. d, p = map(int, input().split()) dp = [0 for _ in range(d+ 1)] for _ in range(p): l, c = map(int, input().split()) for x in reversed(range(..

0부터 n까지의 정수 k개를 더해서 n이 되는 경우의 수를 구하는 프로그램 뭔가 고등학교 시절의 자연수 분할이 떠오른다. 차이점은 0도 포함한다는 점 예를들어 0부터 9까지 2개로 나타내면 0+0 1+0, 0+1 2+0, 1+1, 0+2 3+0, 1+2, 2+1, 0+3 4+0, 1+3, 2+2, 3+1, 4+0 5+0, 1+4, 2+3, 3+2, 4+1, 5+0 ... 와 같이 (n,2)=n+1임을 알 수있다. 그리고 잘 보면, 1+ n-1, 2+n-2꼴로 나타 낼 수 있는데, 이를 잘 보면 (n,k)=(n-1,k-1)+(n-1,k-2)...(n-1,0)으로 나타낼 수 있음을 알 수 있다. 가로는 숫자, 세로는 k개로 나타 낸 것이다 0 1 2 3 4 1 1 1 1 1 1 2 1 2 3 4 5 3 1 ..

모든 인접한 수의 차이가 1인 수의 갯수를 찾는 문제 n=1일때, 1,2,3,4,5,6,7,8,9의 9개이다. (0으로 시작은 안되므로 제외) n=2일때, 10 21 32 12 23 43 54 34 65 45 56 76 67 87 78 98 89 90의 17개이다. 여기서 잘보면, n이 1일때의 두배에서 -1한 것임을 알 수 있다. 이게 n=3일때도 잘 작동해서 일반항이 n(k)=n(k-1)-(k-1)인지 알았으나 5부터 잘 작동하지 않았다. 그렇다면, 일반항을 따로 구할 수 없으니 케이스를 쪼개서 이전값에서 받아오자. 규칙을 찾으면, 어떤 수가 n으로 끝난다면, n으로 끝나는 수의 갯수는 이전 수의 n-1로 끝나는 수와 n+1로 끝나는 수의 갯수의 합이라는 것이다. 여기서 특이 케이스가 보이는데 바로 ..

드디어 dp도 감이 잡혀가는 듯 하다. 물론 다른 문제 풀면 또 아닌걸 느끼겠지만 미로를 오른쪽 아래로 가면서, 가장 사탕을 많이 챙기는 경우의 사탕 수를 구하는 문제 반복문을 돌리면서 현재값=max((x,y-1),(x-1,y),(x-1,y-1))+현재 사탕수 를 해주어 이전값의 최대값+현 사탕수를 구해준다. 다만, 벽 가장자리에 위치한 사탕의 경우 이전값을 구하기가 어려우므로 예외처리 해주었다. 이게 실버 1이라고? 하는 생각이 들었던 문제. import sys input=sys.stdin.readline n,m=map(int,input().split()) ma=[] for x in range(n): ma.append(list(map(int,input().split()))) dp=[[0 for x in..

실버 1이 무색할 정도로 정석적인 dp문제가 아니었나.. 첫 입력값을 d1, 두번째 입력값을 d2라고 하자. D(3)=d1+d2 D(4)=D(3)+D(2) D(5)=D(4)+D(3) 으로 분해 할 수 있다. 따라서 일반항은 D(n)=D(n-1)+D(n-2) 그러면 결국 예제 입력 [6, 41]에 대해서 D(6)=D(5)+D(4)=......3d1+5d2=41이라는 식을 갖게 된다. d1에 대입을 하다 보면 d1=2, d2=7이 된다. 나는 전역 변수를 통해 d1, d2를 세주고, 방정식의 해가 나올 시에 바로 출력을 끝내게 만들었다. import sys sys.setrecursionlimit(100000) d,k=map(int,input().split()) d1,d2=0,0 def dp(n): globa..

식보다는 관계가 중요했던 문제. 점화식을 세우는 것 보다는 현재값은 이전 값들의 합이라는 관계가 더 중요했던 문제다. n이 2보다 큰 상황에서, 1은 2,4에서 온다. 2는 1,3,5에서 온다. 3은 2,6에서 온다. 4는 1,5,7에서 온다. 5는 2,4,6,8에서 온다. 6은 3,5,9에서 온다. 7은 0,4,6에서 온다. 8은 5,7,9에서 온다. 9는 6,8에서 온다. 따라서 이전 값들의 합을 따로 저장했다가 더해서 현재값에 덧씌워 주면 된다. t = int(input()) for _ in range(t) : n = int(input()) num = [1 for x in range(10)] for _ in range(1,n) : n=num[:] num[0] = n[7] num[1] = n[2] +..

요약하면, 무게가 커지고, 선명도 값이 감소하는 최장수열을 구하라는 것 여타 다른 dp문제와 동일하되, 두가지 값을 동시에 비교한다. 반복문을 통해 0부터 n까지 기준값을 높히고, 0부터 x까지 비교값을 바꿔가며 무게와 서명도를 비교하고, 그에따라 compare 배열에 값을 바꿔준다. 출력은 compare의 최대값을 출력해주면 된다. t=int(input()) for _ in range(t): n=int(input()) compare=[1 for x in range(n)] w=[] c=[] for _ in range(n): a,b=map(float, input().split()) w.append(a) c.append(b) for x in range(n): for y in range(x): if w[x]>..

수를 1로 만드는 최소값을 구하되, 만드는 방법도 출력하라는 문제 간단하게 최소 방법은 3으로 나눠지면 3으로 나눈 dp값과 현재값을 비교해서 초기화, 2로 나눠지면 2로 나눈 dp값과 현재 값을 비교해서 초기화, 둘다 안되면 -1한 dp값과 현재 값을 비교해서 초기화. 문제는 방법이다. 나는 m이라는 2차원 리스트를 만들어서 dp값을 초기화 할때 그 값에 맞춰서 이전 경로를 추가하고, 이전 숫자를 추가하는 식으로 경로를 저장했다. 출력시에는 출력하는 숫자+m에 저장된 경로를 출력시켰다. n=int(input()) dp=[99999999 for x in range(n+4)] m=[[] for x in range(n+4)] dp[0],dp[1]=0,0 dp[2],dp[3]=1,1 m[0]=[0] m[1]=..

15988과 거의 유사한 문제, 다만 연속해서 사용할 수 없다는 것이 차이점이다. https://0422.tistory.com/71 15988 백준 파이썬 DP는 나열이 반이다. 잘 나열하는게 시작이다. 그럼 1부터 5정도까지만 나열해보자. 1 2 3 4 5 1 1+1 2 1+1+1 1+2 2+1 3 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 1+1+1+1+1 1+1+1+2 1+1+2+1 1+1+3 1+2+1+1 1+2+2.. 0422.tistory.com dp는 역시 나열이다. 1부터 6까지 나열해 보자. 1 2 3 4 5 6 1 2 1+2 2+1 3 1+2+1 1+3 3+1 1+3+1 2+1+2 2+3 3+2 1+2+1+2 1+2+3 1+3+2 2+1+2 2+1+3 2+3+1..