본문 바로가기

DP

 (57)
[Python] 23325번 마법천자문 https://www.acmicpc.net/problem/23325 23325번: 마법천자문 최근最近 만화漫畫 마법천자문魔法千字文을 감명感銘 깊게 읽은 연두然斗는, 모든 수數를 한자漢字로 적기 시작始作했다. 그런데 수업授業을 들으면서 필기筆記 해놓은 내용內容을 복습復習 www.acmicpc.net 24/02/08 업 다운 랜디를 하다 만난 문제로, 처음에 어떤 알고리즘을 적용해야 할 지 몰라 많이 헤맸던 문제다. 문제 접근 방식: 처음에 접근했던 방식은 무지성 dfs였다. 열심히 짰지만 당연히 시간초과가 났다. 태그를 까고 곧바로 어떻게 풀지 알아버렸는데, 태그는 DP였다. 상태 식은 다음과 같이 정의된다. $$DP[i] = i\textrm{번째 문자까지 보았을 때 해석할 수 있는 가장 큰 계산 결과}$..
[Python] 10978번 기숙사 재배정 https://www.acmicpc.net/problem/10978 10978번: 기숙사 재배정 N이 4인 경우, 봄학기 때 4명의 학생 (민수, 동화, 갑도, 석주)이 각각 기숙사 A,B,C,D에 배정이 되었다면, (민수-B, 동화-A, 갑도-D, 석주-C), (민수-B, 동화-C, 갑도-D, 석주-A), (민수-B, 동화-D, 갑도-A, 석주 www.acmicpc.net 23/12/08 단순 교란 순열 문제이다. 알면 매우 쉽게 해결할 수 있다. 문제 접근 방식: 그냥 문제를 보면 교란 순열의 개수를 구하는 것과 같음을 알 수 있다. 교란 순열에 대한 간략한 설명은 다음 링크를 참고하자. https://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84%EC%88%9C%EC%97..
[Python] 17953번 디저트 https://www.acmicpc.net/problem/17953 17953번: 디저트 창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 ‘차라리 케이크를 먹는게 나 www.acmicpc.net 23/09/26 무난한 2차원 DP문제로, DP 테이블의 의미를 생각하면 쉽게 점화식을 세울 수 있다. 문제 접근 방식: 문제를 보면 전날에 먹었던 디저트와 같은 디저트를 먹으면 그 날에 얻을 수 있는 만족감보다 절반의 만족감만을 얻을 수 있다고 했다. 특정한 날에 디저트를 먹을 수 있는 선택지가 최대 $M = 10$까지의 제한이 있으므로, 즉, 최대 10개의 디저트가 선택지로 놓여있으므로, 이를 브루트포..
[Python] 1562번 계단 수 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 23/12/05 비트마스킹을 이용한 DP를 연습하기 좋은 문제이다. 클래스 5에도 있으니, 비트마스킹에 대한 개념을 이해한 뒤에 조금 생각해보고 풀면 더욱 도움이 될 것 같다. 문제 접근 방식: 길이가 매우 긴 자리수를 가지고 있는 특정한 계단 수에 대한 경우의 수를 구하는 문제이다. 계단 수이긴 하지만, $0$부터 $9$까지의 모든 숫자를 써야 한다는 점이 다르다. 즉, 우리는 숫자의 사용 여부를 관리해야 할 필요성이 있다. 그걸 DP 배열에 넣고 관리하기에는 조금 까다로운 면이 있다. 이럴 때 비트마스킹을 이용할 수..
[Python] 4811번 알약 https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 23/07/05 카탈란 수임을 알면 쉽게 풀 수 있고, 그게 아니더라도 2차원 DP로 쉽게 해결할 수 있다. 문제 접근 방식: 반 조각을 꺼내는 행동은 이전에 한 조각을 꺼내는 행동이 수반되었어야만 나올 수 있다. 따라서 이건 카탈란 수열임을 확인할 수 있다. 한편, 그냥 2차원 DP로도 접근할 수 있다. $DP[i][j]$ = 현재 $i$일이고, 반조각을 꺼낼 수 있는 횟수가 $j$번일 때의 문자열 개수 라고 ..
[Python] 10422번 괄호 https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 23/05/07 카탈란 수 기본 문제다. 문제 접근 방식: 조합론에서 카탈란 수는 매우 매우 매우 중요한 수 중 하나이다. 괄호 문제의 경우, 카탈란 수 예시 중 가장 첫 번째로 나오는 예시인 만큼 알아 두어야 할 것이다. 카탈란 수의 점화식을 그대로 구현하면 끝이다. 점화식은 다음과 같다. $$C_n = C_0C_{n-1} + C_1C_{n-2} + \cdots + C_{n-1}C_0$$ 아래..
[Python] 9343번 랜덤 걷기 https://www.acmicpc.net/problem/9343 9343번: 랜덤 걷기 각 테스트 케이스 마다 음수 좌표를 방문하지 않고 시작점으로 도아오는 랜덤 걷기의 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 23/12/07 누가 봐도 그냥 카탈란 수 문제다. 문제 접근 방식: 누가 봐도 그냥 카탈란 수 문제인데, 이건 제한이 크기 때문에 카탈란 수의 점화식으로 구현하면 안된다. 일반항으로 접근해야 되는데, 모듈로 역원을 활용하여 구현할 수 있다. 파이썬은 모듈로 역원을 pow함수를 통해 쉽게 구할 수 있으니 이를 잘 활용해 보자. 카탈란 수의 일반항은 다음과 같다. $$C_n = \frac{1}{n+1} \binom{2n}{n}$$ 아래는 내가 위..
[Python] 21739번 펭귄 네비게이터 https://www.acmicpc.net/problem/21739 21739번: 펭귄 네비게이터 펭귄은 현재 ($1$, $1$)에 있다. 펭귄은 집까지 가고 싶다. 펭귄의 집은 ($2$, $N$)이다. 하지만 누군가에 의해 얼음길이 다 깨져 집에 갈 수 없게 되었다. 현진이는 펭귄들을 위해 얼음길을 만들어줄 www.acmicpc.net 23/12/06 이것도 카탈란 수임을 알면 매우 쉬운 문제이다. 문제 접근 방식: 이 문제는 카탈란 수 임을 알아내는게 조금 까다롭다. 영 타블로를 잘 알고 있는 사람이라면 이 그림이 $2 \times n$짜리 영 타블로의 개수이고, 이를 계산하면 카탈란 수라는 사실을 알 수 있다. 근데 이건 좀 더 나아간 설명이고, 그림을 살펴보면, "항상" 윗 줄보다 밑 줄의 원소가..

티스토리툴바