그냥 하는 노트와 메모장

BOJ 2995 생일 [분류 : 세그먼트 트리] [풀이] [좌표평면] 구간의 왼쪽들을 x축으로, 구간의 오른쪽들을 y축으로 생각해보자. 좌표평면으로 옮긴 두 구간을 비교할 땐 두 점을 비교하는 걸로 동치로 볼 수 있다. 둘 중에 한 점이 x축이 작고 y축이 크면 다른 한 점(구간)을 포함한다라고 볼 수 있다. [정렬] 세그먼트 트리 갱신해야하기 때문에 정렬을 수행한다. 나는 x축을 비오름차순으로, y축을 비내림차순으로 접근했다. 이렇게 접근하면 방문하고 있는 x좌표는 지금까지 방문한 좌표들보다 무조건 작거나 같으므로 구간을 포함할 수 있는 가능성을 열어두게끔 한다. 반대로 y좌표는 같거나 작아야하는 좌표들 중 가장 큰 값을 가져와야하므로 구간 최대를 가져오기 위해 세그먼트 트리를 사용한다. 더보기 #in..

배낭 문제(냅색) 시리즈 - 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,..

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와 가장 가까운 정수를 출..

* BOJ 16876 재미있는 숫자 게임[분류 : 다이나믹 프로그래밍] [풀이] 턴 수의 홀짝 여부를 따져서 누가 게임을 끝내는지 쉽게 알 수 있다. 따라서 기저 조건에 게임이 종료될 때 누가 이기는지 결정한다. 서로 이기려고 최선을 다한다는 조건이 있기 때문에 어느 턴(p)에 어떤 수(d)로 주어지는 경우에 수행할 수 있는 행동은 1~10^3자리 숫자를 1 증가하는 4개밖에 없으므로 for문 한 번 구성해서 돌려주면 된다. 9에서 다시 0으로 간다는 조건만 잘 구현하면 어렵지 않게 AC를 받을 수 있는 문제다. #include #include int dp[101][10000], N, M, dx[] = { 1,10,100,1000 }; int rec(int p, int d) { if (p == M) re..