baekjoon 10775 공항 10775번 공항 접근 문제 크기게 굉장히 크기 때문에 일단 dp는 될 수 없다고 생각했다. 처음엔 1번째 gate부터 넣고 더 여유있는 비행기들이 뒤로 옮기는 방식으로 했다. 왜 처음부터 가장 자기가 갈 수 있는 최대로 안갔냐고 묻는다면 어짜피 거기서도 많이 차면 아래로 한칸씩 내려와야한다고 생각했다. 하지만 이렇...

baekjoon 1766 문제집 1766번 문제집 접근 처음보자 마자 위상정렬 문제라는 것을 알 수 있었다. 한 가지 다른 점이라면 이 문제에선 더 쉬운문제를 먼저 풀어야 하므로 우선 순위 큐를 이용해서 항상 가장 작은 수를 뽑아내도록 했다. 코드 //1766 #include <iostream> #include <queue&gt...

baekjoon 11409 행렬 곱셈 순서 11409번 행렬 곱셈 순서 접근 dp를 한다는 것은 결국 다 해본다는 뜻이다. ac25683번 처럼 단조감소가 있으면 그리디로 풀리겠지만 그렇게 단조감소부분을 제거하고 나면 결국은 dp이다. 모든 경우를 단순히 다 해보는 방법은 순열로 각 곱하기를 줄세우는 것이니 500!의 시간복잡도가 걸린다. 무조건 ...

baekjoon 1202 보석 도둑 1202번 보석 도둑 접근 크기가 너무 크기 때문에 dp는 절대 아니라고 생각했다. 생각해보니 크기가 작은 가방부터 채우되, 각 가방에 들어가는 보석중 최대 가격을 채우면 될 것 이라고 생각했다. 이를 구현하기 위해 vector로 for문을 계속 돌리면 O(n^2)의 시간복잡도를 가지게 된다고 생각했다. 그런데 ...

baekjoon 1423 원숭이 키우기 1423번 원숭이 키우기 접근 처음엔 어떻게 dp를 시킬지가 머리에 들어오지 않았다. 항상 dp가 현재 각 캐릭터가 몇명 있는지를 status로 다 들고 있어야할 것 같은데 그럼 너무 경우의 수가 많아져 dp를 쓰는 이유가 없어진다. 그러다가 dp(i) = i일 훈련 시켰을 대의 최댓값으로 정의하고 dp안에다...

baekjoon 21757 나누기 21757번 나누기 접근 처음에는 dp(x)를 x가 지금 바라보고 있는 원소 index일 때 x~n-1의 원소 중 정해진 groupSum의 합을 갖는 그룹으로 나누는 가짓수로 정의했다. count도 안넣었던 것이 어짜피 나머지 원소 전체의 합이 있을 때 이를 groupSum으로 나누면 몇 개의 group으로 나뉠지...

baekjoon 1023 괄호 문자열 1023번 괄호 문자열 접근 dp(frontOpen, empty) = 지금까지 닫히지 않은 “(“가 frontOpen개 있고 채워야 하는 빈칸이 empty개 있을 때 경우의 수이다. dp(frontOpen, empty) = dp(frontOpen+1, empty-1) //”(“추가한 경우 ...

baekjoon 1256 사전 1256번 사전 접근 이 문제도 dpSkip문제이다. dp(n, m) = “a” n개, “z” m개로 이루어져있는 문자열 개수 dp(n, m) = dp(n-1, m) + dp(n, m-1) skip(n, m)에서 skip < dp(n-1, m)이면 a로 시작 아니면 z로 시작 코드 //1256 #include ...

baekjoon 2248 이진수 찾기 2248번 이진수 찾기 접근 dp의 2번째 유형이다. k번째 수를 찾으라고 하는 dp이다. 직접 1번째부터 k번째 까지 다 찾게 되면 너무 오래걸리기 때문에 skip을 이용해서 뛰어 넘어서 구한다. 그 뛰어 넘을려면 경우에 맞는 수를 직접 다 나열하는 것이 아닌 dp를 이용해서 바로 개수만 return 하도록 ...

baekjoon 2533 사회망 서비스(SNS) 2533번 사회망 서비스(SNS) 접근 핵심은 tree를 만든 상황에서 이웃한 두 vertex 중 최소 하나는 색칠(얼리어답터)되어야 한다는 것이다. 그래서 이건 tree에서의 dp로 현재 vertex와 전 vertex가 색칠되었는지의 여부가 dp에 들어간다. 코드 //2533 #include &...