DP12 BOJ7812 중앙 트리 7812번 중앙트리 트리와 각 간선의 가중치가 주어질 때 한 꼭짓점에 대해 모든 꼭짓점과의 거리 합이 최소일 때의 그 값을 구한다. 즉 중앙 정점과 모든 꼭짓점과의 거리 합을 구한다. DFS, DP 당연히 모든 점에 대해 거리를 다 계산해볼 순 없고 트리이므로 DFS, 중앙 정점이 될 수 있는 점을 DP로 찾아가며 푼다. 처음에 DFS 두 번에 푸는 방법으로 해결했는데, 한 번만으로도 충분했다. 일단 간선은 벡터 E에 간선을 { 자식 노드 , 가중치 } 로 저장한다. DFS 두 번 하는 방법: 트리 먼저 만들고, 중심을 옮길지 말지 결정 0을 기준으로 모든 정점의 거리 합을 계산한 후 0보다 하위인 정점이 중앙 정점이 될 수 있는지 판단 1. 0에서 DFS, 모든 정점과 0사이의 거리 합 계산 이때 각 .. 2021. 7. 30. BOJ1949 우수 마을 1949번 우수 마을 N개의 마을로 이루어진 트리 형태의 나라에서 우수 마을인 두 마을이 인접하지 않고 우수 마을이 아닌 마을은 적어도 한 우수 마을과 인접해야 할 때 우수 마을로 선정된 마을 주민 수의 최댓값을 구한다. Tree + DP 2535번과 비슷하다. 다만 2535번에서는 v가 선택될 때/아닐 때 두 가지만 고려하면 됐는데 여기서는 v의 자식노드까지 생각해야 한다. 좀 더 상위버전인 듯. 우수마을을 선정하는 조건을 파악하자 1. 우수 마을인 두 마을이 인접하지 않는다. v가 우수마을이면 v의 모든 자식 노드는 우수 마을이 될 수 없다. 2. 우수마을이 아닌 마을은 적어도 한 우수 마을과 인접하다. v가 우수마을이 아니라면 v의 자식 노드 중 하나가 우수 마을이거나, v의 부모 노드가 우수 마을.. 2021. 6. 10. DP (1) Dynamic Programming 다이나믹 프로그래밍 BOJ1028 다이아몬드 광산 R*C 크기로 주어진 광산에서 가장 큰 ◇ 모양의 다이아몬드의 크기(한 변의 길이)를 구한다. ↖,↗ 방향으로 연속한 1의 개수를 구하고 다이아몬드의 아래 꼭짓점을 기준으로 최대 다이아몬드 크기를 구한다. dp[ i ][ j ][ 0 ] ( i , j )기준 ↖방향으로 연속한 1의 개수 dp[ i ][ j ][ 1 ] ( i , j )기준 ↗방향으로 "" 이때 아래 꼭짓점이 ( i , j )이고 크기가 k+1인 다이아몬드가 존재하려면 아래 조건을 만족해야 한다. dp[ i ][ j ][ 0 ] > k dp[ i ][ j ][ 1 ] > k dp[ i-k ][ j-k ][ 1 ] > k dp[ i-k ][ j+k ][ 0.. 2021. 6. 10. BOJ1014 컨닝 1014번 컨닝 N*M크기의 직사각형 교실에서 컨닝을 방지하도록 앉힐 수 있는 최대 학생 수를 구한다. 현재 위치를 기준으로 동일 행의 좌우(←→), 윗 행 좌우 대각선(↖↗) 위치의 답지를 베낄 수 있다. 비트마스킹 + DP 학생이 앉은 상태, 앉을 수 없는 자리 등을 bit로 표현하고 i행에서 k의 상태로 앉을 수 있는 학생 수의 최댓값을 i-1행을 고려해 구한다. * 3줄 요약 cnt[ k ] 행의 상태가 k일 때 해당 행에 앉는 학생의 수 (= k를 이진수로 나타낼 때 1의 개수) dp[ i ][ k ] i행에 k의 상태로 앉을 때의 최대 학생 수 dp[ i ][ k ] = dp[ i-1 ][ up ] + cnt[ k ] (up은 i행의 상태가 k일 때 i-1의 상태로 가능한 것 중 dp값이 가장.. 2021. 5. 19. BOJ1086 박성원 1086 박성원 길이 50 이하의 자연수가 N(≤15)개 주어질 때 주어진 모든 자연수를 한 번씩 사용하여 이어 붙여 만든 자연수가 100이하의 자연수 K로 나누어 떨어질 확률을 구한다. example. (A) N=3 K=27 { 104, 4, 90 } 104490 104904 410490 490104 901044 904104 여섯 개 중 세 개만 나누어 떨어지므로 1/2 출력 (B) N=3 K=13 { 12, 2, 2 } 1222 1222 2122 2212 2122 2212 여섯 개 중 두 개만 나누어 떨어지므로 1/3 출력 * s[0]="12", s[1]="2", s[2]="2"일 때, s[0]+s[1]+s[2]="1222"와 s[0]+s[2]+s[1]="1222"를 모두 세야 한다. (순열 방식이 .. 2021. 4. 21. KMP DP 트리 그래프 기하학 최근 푼 문제 1701 Cubeditor KMP idx(0~N-1)부터 N까지의 부분문자열에 대해 Pi를 구한다. idx에 대하여 최대 Pi값 - idx = 두 번 이상 나오는 가장 긴 부분문자열의 길이 * Pi를 구하는 시작점의 인덱스가 0이 아님에 주의해서 풀면 됨 16900 이름 정하기 KMP 주어진 문자열 S가 최소 K번 부분문자열로 등장하는 새로운 문자열 길이의 최솟값을 구한다. Pi를 구해 문자열 S에서 K-1번 반복해줄 부분 문자열을 구한다. 아래는 예시 S ada 3 pi 001 => (3-2)+2*3 S abc 2 pi 000 => (3-3)+3*2 S rr 5 pi 01 => (2-1)+1*5 S abcabcabca 3 pi 0001231234 => (10-3)+3*3 1509 팰린드롬 분할 DP 주.. 2021. 4. 16. BOJ10714 케이크 자르기 2 10714번 케이크 자르기 2 자를 수 있는 케이크 조각의 크기가 주어질 때, JOI는 최선을 다해 케이크를 자르고, IOI는 양 끝 조각 중 무조건 큰 조각을 자른다. JOI가 얻을 수 있는 조각 합의 최댓값을 구해야 한다. 최선을 다하는 문제와 비슷하다. 다른 점은 JOI만 최선을 다한다 ⇒ dp배열에 두 명이 가진 케이크 양을 저장할 필요 없이 JOI가 얻게 된 조각 합의 양만 저장하면 된다. 케이크 조각은 직선형 배열이 아닌 원형 배열이다. 즉 시작과 끝이 정해져있지 않다 ⇒ i, j의 대소에 관계없이 전체 dp 배열을 채워야 한다. 가령 N=5일 때 dp[ 2 ][ 4 ]는 2, 3, 4번째 조각이 남아있을 때 dp[ 4 ][ 2 ]는 4, 5, 1, 2번째 조각이 남아있을 때 JOI가 얻은 케.. 2021. 1. 30. BOJ2342 Dance Dance Revolution 2342번 DDR 뭔가 경찰차랑 비슷한 느낌의 DP 눌러야하는 DDR의 발판 번호가 주어지면 발판을 순서대로 누르기 위한 최소의 힘을 구해야 한다. a[ i ][ j ]=이번 발판까지 고려하여 오른발이 i, 왼발이 j를 누를 때 사용한 최소의 힘 STEP 1. 발의 움직임에 따라 사용하는 힘을 배열에 저장 사차원 배열을 이용했다. p[ a ][ b ][ c ][ d ]=오른발 a, 왼발 b에서 오른발 c, 왼발 d 가 될 때 사용하는 힘 //same posit: 1i,j -> i,j i=0-4 j=0-4 //0->1/2/3/4: 2i,0 -> i,j i=0-4 j=1-4 //moving adj: 3i,j -> i,j+1 //moving opp: 4 //STEP 1. Set Power p int p[5][.. 2021. 1. 30. BOJ2618 경찰차 BOJ2618 경찰차 dp[ i ][ j ] dist = 마지막으로 A, B가 각각 i, j를 처리했을 때 움직인 총 거리 T = 가장 최근 사건을 처리하기 직전의 상태 STEP 1. w=1일 때 dp[ 1 ][ 0 ], dp[ 0 ][ 1 ] 갱신한다. STEP 2. w=2~W일 때 dp[ * ][ w ]와 dp[ w ][ * ]를 구한다. w-1번째, w번째 사건을 처리하는 경찰차가 각각 무엇인지에 따라 구해주면 된다. A-A: [ w-1 ][ * ] → [ w ][ * ] A-B: [ w-1 ][ * ] → [ w-1 ][ w ] B-A: [ * ][ w-1 ] → [ w ][ w-1 ] B-B: [ * ][ w-1 ] → [ * ][ w ] ㆍ*에 들어갈 수는 0부터 w-2까지여야 한다. ㆍdis.. 2021. 1. 29. BOJ13976 타일 채우기 2 BOJ13976 타일 채우기 2 BOJ2133 타일 채우기 같은 문제다. 다만 N의 범위가 다르다. 2133번은 1≤N≤30이기 떄문에 수열의 값을 모두 구해도 된다. 13976번은 1≤N≤1,000,000,000,000,000,000=10^18이기 때문에 행렬의 거듭제곱을 이용하여 풀어야 한다. 필기만 옮기려고 했으나 코드까지 첨부 더보기 #include #include using namespace std; long long DIV = 1000000007; struct Matrix { long long a[2][2]; Matrix() { a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0; } Matrix(long long x, long long y, long long z, lo.. 2021. 1. 28. 이전 1 2 다음
