그냥 하는 노트와 메모장

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,..

BOJ 12861 죄수에게 주는 뇌물 [분류 : 다이나믹 프로그래밍] [풀이] [첫번째] 가장 처음에 Q[i]번째 죄수를 석방했다고 해보자. 그러면 1번째 죄수부터 Q[i]-1번째 죄수까지, Q[i]+1번째 죄수부터 P번째 죄수까지 모두 뇌물을 줘야한다. [그 이후의 석방] 이제 죄수를 고를 때 Q명의 죄수 중 i번째를 석방시켰으니, 이젠 구간을 나눠서 봐야한다. 구간 [1, Q[i]-1]에서 Q명의 죄수 중 누굴 석방할 것인지 구간 [Q[i] + 1, P]에서 Q명의 죄수 중 누굴 석방할 것인지 [간단한 dp 아닌가 ?] 그러면 두 구간을 모두 다룰 수 있도록 구간 [l, r]에 대해 부분 문제를 (l, Q[i]- 1) + (Q[i]+1, r)로 두면 되지 않나? 싶은데, 모든 감옥을 인덱스로 담기에는..

* BOJ 1023 괄호 문자열[분류 : 다이나믹 프로그래밍] BOJ 17428 K번째 괄호 문자열을 먼저 푸는 것을 추천합니다. 사실상 거의 같은 문제입니다. [풀이] 올바른 괄호 문자열의 정의는 '('의 수와 ')'의 수가 같아야하며 왼쪽에서 오른쪽으로 순회할 때 ')'의 수가 '('의 수보다 많아지면 안된다. 반대로 괄호 ㄴㄴ 문자열이 되려면 위 정의 반대로 구성하면 된다. 즉, 1. '('의 수와 ')'의 수가 다르거나 2. 왼쪽에서 오른쪽으로 순회할 때 ')'의 수가 '('보다 많은 경우에 올바르지 않다고 판단해주면 된다. 위를 토대로 함수 프로토타입을 정의하면 아래와 같다.rec(v, p, r) v : validation ')'의 수가 '('의 수를 역전했던 적이 있는지 확인하는 플래그 변수p..

* BOJ 17428 K번째 괄호 문자열[분류 : 다이나믹 프로그래밍] [풀이] 올바른 괄호 문자열이 몇 개 있을 수 있는지 생각해보자. 당연히 이 문제를 풀어본 사람은 카탈란 수를 떠올릴 수 있을거고, 아니더라도 아래 점화식을 떠올릴 수 있다. 하지만 이런 방식은 사전순에 대한 처리를 할 수 없어진다. 보다 간단하게 생각해보자. 현재 위치에서 어떤 괄호를 쓸 것인지를 생각해보자. 단 지금까지 구성해온 문자열에서 모두 쓸 수 있는 것은 아니다. '('과 ')' 수가 똑같을뿐만 아니라 왼쪽에서 오른쪽으로 순회할 때 ')' 수가 '(' 수보다 많지 않도록 구성해야 한다. 따라서 정의해야 하는 함수는 현재 위치 p에서 '('가 ')'보다 r만큼 많을 때 나올 수 있는 올바른 괄호 문자열의 수를 반환하도록 한다..

* BOJ 3001 이상한 문제[분류 : 다이나믹 프로그래밍] [풀이]1. [각 자리수 합이 S인 개수] 구간이 정해져 있으므로 1부터 B까지 합이 S인 것의 개수에서 0부터 A-1까지 합이 S인 것의 개수를 빼준다. 이렇게하면 똑같은 함수를 두 번 호출하는 꼴이 나온다. rec(limit, position, summation, A)※ limit은 주어진 A보다 작은 경우만 세야하므로 제한을 두는 변수다. 기저영역은 A보다 작은 자리수에 대해 숫자를 채웠고 남은 summation이 0이 되는 경우에 1 더해주면 된다. 2. [A보다 크거나 같고 B보다 작은 수 중 자리수 합이 S가 되는 가장 작은 정수] 문제 조건에서 적어도 하나 이상의 수가 반드시 존재한다고 했으니 이 값은 A와 가장 가까운 정수를 출..