그냥 하는 노트와 메모장

BOJ 8902 색상의 길이 [분류 : 그리디, 다이나믹 프로그래밍] [풀이] 하나의 색에 대해서만 생각해보자. 합쳐질 차선에 배치할 때 그 색상 중 가장 왼쪽에 올 수 있는 1차선의 후보와 2차선의 후보를 가려내보자. 순서상 같은 차선에서 같은 색상을 가지는 인덱스 i 3 a=5, F[0][a] -> 6 dp[a][b]=현재 1차선에서 a번째 후보와 2차선에서 b번째 후보를 사용할 수 있을 때 만족하는 최소 거리 (거리를 계산해야하는 색의 수) 나는 후보를 하나씩 사용하면서 거리를 계산했다. 현재 후보군 위치가 (a, b)이므로 이 이전에 사용한 데이터를 가지고 현재 어떤 색상을 쓰고 있는지(이하 usedCnt) 또 그 색상을 모두 배치 했는지(이하 doneCnt)을 알 수 있다. 각 색마다 가장 왼쪽..

BOJ 1226 국회 [분류 - 다이나믹 프로그래밍, 그리디] [풀이] 당을 하나씩 추가하면서 전체의 절반을 초과하는 경우를 봐야한다. $$a_i=의석수$$ $$total=\sum_{i=1}^{n} a_i$$ $$ half=\lfloor{total/2}\rfloor $$ [접근] 0부터 half까지 순회하면서 현재 좌석수를 더해줌으로 절반을 초과하는지 확인하면된다. [그리디] 단, 좌석수 기준 비오름차순으로 정렬한 데이터를 가지고 추가해야한다. 조건에서 보면 현재 좌석 수를 x로 구성했을 때 x를 만들기 위해 연합된 당들 각각 하나를 빼면 좌석수가 절반 이하이어야만 한다. 현재 당의 좌석수가 ci라고 할때 현재 당을 제외한 나머지 당으로 half를 구성했다고 치자. 그러면 half + ci도 정답 후보가..

BOJ 18892 가장 긴 증가하는 부분 수열 ks [분류 : 다이나믹 프로그래밍] [풀이] [시작과 끝] 시작과 끝점이 K에 따라 달라질 수 있다. 모든 경우를 생각하기 귀찮으니 시작과 끝을 고정시키기 위해서 0번째에 충분히 작은 값(-10^9)을, N+1번째엔 충분히 큰 값(10^9)을 넣어주고 LIS를 구하자. 배열 A중에 0번째보다 작거나 N+1번째보다 큰 값은 존재할 수 없기 때문에 이 상태로 LIS를 돌려도 똑같은 답을 구해낼 수 있다. [추적] 0번째부터 시작해서 K번째 LIS를 찾아간다. 대신 사전순으로 처리해야하기 때문에 갈 수 있는 인덱스 구간을 정렬해주자. set을 이용하면 삭제도 편하고 정렬도 알아서 해주니 편하다. 정렬된 데이터에 대해 i번째에 접근했다고 하자. 그러면 세 가지 경..

BOJ 2507 공주 구하기 [분류 : 다이나믹 프로그래밍] [풀이] [O(N^3) 메모리] 가장 간단하게 p번째 섬을 출발 경로 또는 귀환 경로에 포함할지를 판단하는 dp를 생각할 수 있다. 하지만 이는 메모리 O(N^3)를 잡아 먹기 때문에 불가능하다. [접근 아이디어] 이런 왕복문제의 경우 시작점에서 도착점으로 가는 경로를 생각하자. 즉, 시작점은 항상 하나고, 도착점도 항상 하나로 두고 그 상태에서 서로 다른 경로를 구하면 그것이 곧 갔다가 오는 경로를 모드 셈해주는 것과 같다. [도달 검사] 첫 번째 섬을 제외한 나머지 섬은 반드시 한 번만 밟을 수 있기 때문에 왕복을 위해선 서로 다른 경로 두 개를 구성할 수 있는 경우의 수로 문제를 변형할 수 있다. 단, 한 경로는 현재 섬에서 현재 섬보다 ..

BOJ 4457 상근이의 자물쇠 [분류 : 다이나믹 프로그래밍] 독특한 문제 [풀이] [경우의 수] 트리를 구성할 때 트리 자체의 높이 h를 고정했다고 보자. 그러면 그 높이 h에서 n개의 노드를 배치해야 한다. h를 만드려면 현재 루트가 되는 노드를 제외한 두 서브 트리 중 하나가 반드시 높이 h-1를 가져야한다. 또 조건에서 두 서브 트리의 높이 차이는 1이하이어야 하므로 경우의 수는 세가지가 나온다. 왼쪽 서브 트리의 높이가 h-1, 오른쪽 서브 트리 높이가 h-1 왼쪽 서브 트리의 높이가 h-1, 오른쪽 서브 트리 높이가 h-2 왼쪽 서브 트리의 높이가 h-2, 오른쪽 서브 트리 높이가 h-1 [기저 사례] 기저 사례로는 h가 -1일 때 남은 노드의 수 n이 0이어야만 경우의 수로 포함시키도록 한..

BOJ 12909 그래프 만들기 [분류 : 다이나믹 프로그래밍] [풀이] [노드의 수] 현재 노드 u에서 자식 노드를 추가하는 행위는 전체 사용할 수 노드 수가 줄어든다. 단 그 자식 노드를 루트로 하는 서브 트리의 크기(노드의 수)를 결정해줘야 한다. 당연한 소리지만 현재 N을 사용할 수 있다면 서브 트리의 크기는 최대 N-1다. [상태] 서브트리의 크기가 x라고 하자. 그러면 현재 노드 u에서 추가적으로 사용할 수 있는 노드 수는 N - x가 된다. 자식을 이미 하나 추가했으니 차수는 하나 증가한다. 결국 상태는 (노드 수, 차수)로 볼 수 있다. 노드의 수는 계속 줄어들 수 밖에 없으므로 이 상태를 유지하며 부분 문제를 해결, 부분 구조를 사용해주시면 되겠다. 더보기 #include #include..

배낭 문제(냅색) 시리즈 - BOJ 12865 평범한 배낭, BOJ 12920 평범한 배낭2, Algospot SUSHI [분류 : 다이나믹 프로그래밍] 냅색 문제들을 모아 풀이를 공유하는 포스팅입니다. 이 포스팅은 희한한 냅색 문제들 보는 대로 갱신됩니다. 1. BOJ 12865 평범한 배낭 더보기 일반적으로 알고있는 냅색을 사용하면 된다. 시간 복잡도는 O(NK)가 된다. 재귀적으로 처리해도 좋고, 일차원 배열을 만들어서 큰 값에서 작은 값으로 내려가면서 데이터 오염을 피하며 dp를 구성해도 좋다. #include #include #include using namespace std; const int MAX_N = 100; int N, dp[MAX_N][100001], w[MAX_N], v[MAX_N..

BOJ 10563 정수 게임 [분류 : 다이나믹 프로그래밍] 은근히 어려운 문제.. [풀이] [구간 내의 수 선택] 현재 수를 뽑을 수 있는 구간을 [l, r]이라고 하자. 여기 안에서 조건에 만족하는, 즉 양 옆에 수들 모두 자신보다 작은 후보 집합 S={x | A[x-1] A[x+1]} 중에서 하나 x를 뽑았다고 해보자. [구간 밖의 선택] 그러면 구간은 [l, x), (x, r] 구간으로 나눠지고, 여기서 어느 구간을 선택할지를 고르면 되는데, 1이 존재하는 구간은 반드시 둘 중에 하나밖에 없다. 그 1이 포함되지 않은 구간을 선택하는 경우는 현재 내가 1이 포함되어 있는 구간 중 어느 수를 선택해도 반드시 질 경우에 유효할 수 있다. 가령 구간 [l, x)을 뽑으면 반드시 진다고 ..

BOJ 1555 소수 만들기 [분류 : 다이나믹 프로그래밍, 수학] [풀이] [순열] N개의 수에 대해서 각 자리수에 어떤 수를 둬도 상관없으므로 최대 N!은 먹고 들어간다. (C++에서 next_permutation 사용) [연산 규칙] +,-,*,/ 모두 사칙연산에도 쓸 수 있지만 특히 -는 사칙연산뿐만 아니라 단항 연산에 사용될 수 있다. 즉, 값을 음수면 양수로, 양수면 음수로 바꿀 수 있다. 단순히 두 피연산자 e1과 e2(e1가 왼쪽에 있을 때)가 있을 때 나올 수 잇는 방법은 아래가 있다 e1 + e2 e1 - e2 e1 * e2 e1 / e2 하지만 음수를 붙여주면 경우의 수는 배로 늘어난다. -e1 - e2 -e1 + e2 -e1 * e2 -e1 / e2 보면 1.~4.에 음수를 붙힌 것..

BOJ 1955 수식 표현 [분류 : 다이나믹 프로그래밍] [풀이] 할 수 있는 연산을 생각해보자. 덧셈 곱셈 팩토리얼 여기 세 가지 연산에서 항으로 들어갈 수 있는 표현식도 생각해보자. 대신 마지막 표현식만 생각하자. 표현식을 e1, e2로 둘 때 e1+e2, e1*e2, e1!로 표현이 가능하다. 따라서 n이 주어지면 1.에서는 단순 덧셈으로 구간을 나누고, 2.에서는 약수 판별을, 3.에서는 현재 값이 특정 표현식 e1의 팩토리얼인지 확인해서 다이나믹을 구성해주면 된다. 특정 표현식이라고 표기한 이유는 6! = (3!)!일 수도, (1+5)!일 수도 있기 때문이다. 더보기 #include #include #include using namespace std; const int MAX_N = 1e4 +..

BOJ 15487 A[j]-A[i]+A[l]-A[k] [분류 : 다이나믹 프로그래밍] [풀이] A[j] - A[i]를 먼저 계산해보자. 고정된 j에 대해 A[j]-A[i]가 최대가 되기 위해선 A[i]가 최소이어야 한다. 따라서 j를 순회하면서 [0, j) 구간에서 최소값을 유지하자. 나머지 A[l] - A[k]을 구간 (j, N)에서 구하면 된다. 이 부분은 거꾸로 진행하면 된다. 즉 k를 N-2부터 시작해서 2까지 감소시켜나가면서 A[l]을 최대값으로 유지하며 진행하면 된다. 이렇게 양쪽으로 최소/최대를 유지해나가며 그 중 최대값을 가져오면 AC를 받을 수 있다. 더보기 #include #include using namespace std; const int MAX_N = 1e6; int main() ..

BOJ 2313 보석 구매하기 [분류 : 다이나믹 프로그래밍] 연속 부분 수열의 합을 최대로 하는 방식을 여러 차례 반복해서 진행하면 되는 문제. [주의해야 할 점] 정답은 32비트 int 자료형에 들어가지 않을 수 있다. 오버플로우에 유의하자. 구간의 길이가 짧아야한다. 0인 요소에 대해 처리할 필요가 있다. 가령 "0 0 0 1 0"이 입력으로 들어오면 [1, 4]가 아니라 [4, 4]가 정답 구간이다. 더보기 #include #include #include using namespace std; int main() { int n, L, sum, asum, i, l, r, d, al, ar; long long ans = 0; vector seg; scanf("%d", &n); while (n--) { ..

BOJ 10468 숫자뽑기게임 [분류 - 다이나믹 프로그래밍] [풀이] 일차원 구간 다이나믹이다. 이 문제의 핵심은 구간을 나눌 때 구간의 왼쪽과 구간의 오른쪽은 사용하지 않도록 구성하는 것이다. 즉, 구간의 가장 왼쪽과 가장 오른쪽은 사용하지 않도록 둔다. 구간 사이에 있는 수들 중에서 하나(편의상 i번째)를 골라서 가장 마지막에 제거할 수(Number)로 둬보자. 그러면 그 수를 제외한 가장 왼쪽(l)과 그 수(i), 그리고 가장 오른쪽 수(r)가 남게 되는데 가장 왼쪽과 가장 오른쪽은 선택하지 않기로 했으므로 그 수를 뽑으면 점수는 k[l] + k[i] + k[r]가 추가 된다. 이제 부분 문제는 어떻게 구성하냐면 가장 마지막에 뽑을 수가 i번째 수이므로 rec(l, i)는 왼쪽 구간을, rec(i..

BOJ 5042 나무 옮기기 [분류 - 다이나믹 프로그래밍] (문제 요약) 왼쪽 도로에 나무를 N / 2만큼, 오른쪽 도로에 나무를 N/2만큼 심어야하는데 어떻게 해야 최소로 나무를 움직이면서 계산할 수 있을지가 문제다. [풀이] p번째 나무를 왼쪽 도로에 할당할지, 오른쪽 도로에 할당할지를 결정할 때 나올 수 있는 상태를 현재 왼쪽 도로에 할당할 수 있는 i번째 위치, 현재 오른쪽 도로에 할당할 수 있는 j번째 위치로 볼 수 있다. rec = min(rec(i+1, j) + "왼쪽 도로 i번째에 할당할 때의 거리", rec(i, j+1) + "오른쪽 도로 j번째에 할당할 때의 거리") (참고) p는 i + j로 구할 수 있다. 더보기 #include #include #include using names..

BOJ 12932 노래방 [분류 : 다이나믹 프로그래밍] [풀이] 뭔가 간단한 문제. 현재 p번째 노래를 누가 부를지 결정할 때 나올 수 있는 상태로 영선이가 마지막으로 부른 노래의 인덱스 i, 효빈이가 마지막으로 부른 노래의 인덱스 j가 있다. 몇 번째 노래 해야하는 지(p)를 구할 땐 i와 j 중 큰 값에서 +1를 해주면 구할 수 있다. rec(i, j) = min(rec(p, j) + "i와 p 노래 사이의 난이도", rec(i, p) + "j와 p 노래 사이의 난이도") 더보기 #include #include #include using namespace std; const int MAX_N = 2e3 + 1; int N, dp[MAX_N][MAX_N], A[MAX_N]; int rec(int a,..