그냥 하는 노트와 메모장

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

* BOJ 2543 초고속철도[분류: 다이나믹 프로그래밍] [풀이] 인접한 로봇끼리는 반드시 통신이 가능해야 한다는 점을 유심히 보자. 만약 어떤 로봇 a가 b, c, d, w와 겹치는 상황을 생각해보자. 1. [a에 설치하는 경우] 나머지 b,c,d,w,에 설치할 수도 있고 안할 수도 있다. 2. [a에 설치하지 않는 경우] b,c,d,w에 모두 통신을 설치해야만 한다. [순서도] 1. 먼저 구간 시작 좌표를 기준으로 로봇들을 정렬하자. 정렬하는 이유는 시작 좌표가 낮은 로봇을 기준으로 설치하느냐 마느냐를 결정하여 이후에 있는 로봇에 영향을 미치는 데에 있어 계산하기 용이하기 때문이다. 2. 오름차순으로 방문하며 현재 p번째 로봇에 대해 통신장비를 설치할지말지를 결정해야 한다. 3. 설치한다면 p번째 ..

* BOJ 2888 상범 게임[분류 : 다이나믹 프로그래밍, 구현] [풀이] 구현이 꽤 까다로운 문제. 간단하게 일차원부터 시작해보자. 1. [일차원 - 같은 문자가 딱 두 개] 그 인덱스 차이가 점수가 된다. 2. [일차원 - 같은 문자가 세 개 이상] 점수를 계산할 때 중복해서 셈하면 안된다. 즉, 인덱스 i와 인덱스 j가 같은 문자라면 i에서 j까지의 거리 또는 j에서 i까지의 거리 둘 중 하나만 계산하면 된다. 따라서 편의상 인덱스가 증가하는 순으로 방문하며 이전에 나왔던 같은 문자가 어디에 있었는지를 저장하여 진행하면 된다. 문제는 얼마나 먼 지를 계산할 때 인덱스 자체를 저장하기엔 부담스럽다. 따라서 누적합과 그때까지의 개수를 셈하여 진행한다.(예시) SMMMSSM 에서 S 점수를 구하는 경우..

* BOJ 4384 공평하게 팀 나누기[분류 : 다이나믹 프로그래밍] [풀이] N/2명을 배치하면 나머지 N/2+N%2명은 자동으로 배정된다. 따라서 N/2명이 가능한 점수를 모두 구한 뒤 이를 전체 총합에서 뺀 값과의 차이를 최소화하면 되시겠다. 동전 교환 문제처럼 생각해보자. i번째 사람을 추가하면서 1~N/2명팀을 구성할 때의 값을 구한다. N/2명의 점수 총합의 최대값은 최대 인원수 / 2 * 인원당 최대 점수로 계산 가능하다. 계산해보면 알겠지만, 수 자체가 배열에 담기에 충분히 작기 때문에, i번째 사람을 추가할 때 i-1번째 사람까지 1~N/2명을 팀을 이루도록 했을 때의 "가능한 모든 점수"에서 추가하는 방식으로 진행하면 된다.이렇게 N번째 사람까지 N/2명으로 구성했을 때의 가능한 점수를..

* BOJ 1410 패턴의 개수[분류 : 다이나믹 프로그래밍, 비트셋] 1. [같은 길이의 패턴] 길이가 다른 패턴은 절대 같은 단어를 포함할 수 없다. 같은 길이끼리만 모아서 생각해보자. 2. [비트 셋] 집합의 크기가 아무리 커봐야 15이므로 비트 셋을 쓰기에 충분히 작다. 또 2^15의 배열의 크기로도 충분히 작음을 알 수 있다. 3. [다이나믹 구성] 1.에 있는 조건을 가져와서 같은 길이를 가지는 패턴들만 생각해보자. dp[p][s]=p위치에 있는 문자를 결정해야하고, 현재 겹치는 패턴의 집합이 s일 때, 일치하는 패턴의 수가 정확히 K인 경우의 수 p이전에 선택한 문자들이 모두 일치하는, 또는 문자 ?로 대체할 수 있었던 패턴들이 s 비트 셋에 담겨있다. 현 위치 p에서 문자 a-z를 선택하며..

* BOJ 1176 섞기[분류 - 다이나믹 프로그래밍] [요약] 인접한 사람들의 키 차이가 K초과가 되도록 N명을 배치하는 방법의 수를 구하자 [풀이]1. 이미 i명이 조건에 맞게 서있다고 가정해보자. 이 상태에서 한명을 뒤에 추가하려고 한다. 이때 i명은 조건에 충족하게 이미 서있기 때문에, i명 배치에서 가장 뒤에 있는 사람과 추가할 사람의 관계를 따져 K초과가 될 수 있는지 확인하면 된다.2. 먼저 몇명이 이미 서 있을 때, 맨 뒤에 설 사람을 정한다.3. 다음으로 그 뒤에 누굴 세울지를 정해서 조건에 맞다면 경우의 수를 셈해주면 간단하게 해결할 수 있다. #include #include using namespace std; const int MAX_N = 16; int main() { int N,..

* BOJ 1797 균형잡힌 줄서기 [분류 - 정렬, 그리디] 1. 브루트포스로 계산하기에는 O(N^2)은 시간적으로 부담이되기에 일단 x축을 기준으로 정렬한다. 2. x좌표가 작은 값에서 큰 값으로 순회를 시작하는데, 여자면 -1을 할당하고 남자면 1을 할당하여 누적합을 구한다. 이 때 순회하다가 이전에 나왔던 누적합(bef)이 존재한다면 현재와 bef를 비교하여 x좌표가 얼마나 차이가 있는지 계산한다. 이 값 중에 가장 큰 값을 출력해주면 된다.※ 이 때 누적합이 최초로 등장한 값만 저장해주면 된다. 문제에서 요구하는 것은 x 간격이 가장 큰 것을 원하므로 임의의 누적합이 어디서 최초로 등장했는지를 저장해두고 나중에 다시 이 누적합이 나오면 그것이 곧 최대 간격의 후보를 의미한다. #include #..