MathTrauma

문제 링크 : https://www.acmicpc.net/problem/5905 5905번: 악당 로봇 슈퍼히어로 박승원은 결국 지구를 침략한 악당 로봇들을 해킹하는 데 성공했다. 로봇은 N개의 취약점을 가지고 있는데, (1 ≤ N ≤ 20) i번째 취약점은 'A', 'B', 'C' 로만 구성된 15자 이하의 문자열 S www.acmicpc.net '콤보' 라는 이름으로 패턴들이 주어진다. 검색 대상 스트링이 주어지고 거기에 콤보가 몇 번이나 발생한 것인지를 묻는다면, 평범한 스트링 문제일 것이다. 하지만 길이 K 이하의 문자열로 최대의 콤보가 발생하게 만들어야 하는 상황이니 dp 외에 뚜렷한 방법이 생각나지 않는다. 1. 필요한 정보들 (1) added[i][j] added[i][j] :콤보 i 에 1..

문제 링크 : https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 1. dp 의 정의 좌표 ( i , j ) 에 진입하는 방식에 따라 다음 움직임이 제한된다. 즉, 진입 방향을 기록할 필요가 있다. dir 은 진입 방향을 나타내는데 사용한다. (1, 1) 이 좌측 상단을 위미한다고 할 때, dir=1 은 위에서 아래로, dir=0 은 오른쪽에서, dir=2는 왼쪽에서 진입을 나타낸다. dp[i][j][dir]은 ( 1, 1 ) 에서 이동하..

문제 링크 : https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 1. dp 의 정의 dp[t][p][r] : t 시간에, p 번 나무 아래에서 움직일 수 있는 횟수가 r 번 남아 있을 때의 최댓값. 단, p 는 0, 1 값을 가지고 이는 1 , 2 번 나무를 뜻한다. 주인공 자두는 1 번 나무 아래에서 시작한다는 조건이 있는데 0 초에 0(1 번나무)에서 시작하는 것으로 설계하면 된다. 2. Transition 나무 위치 p 와 t 번째 입력(시간 t 에..

문제 링크 : https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 집합을 표현하거나 본 문제에서처럼 어떤 것들의 사용 여부를 기억할 필요가 있을 때, 비트마스크(bitmask)를 종종 쓴다. 여기서는 0 ~ 9 까지의 사용여부를 bit 로 표현한다.( 중복 사용이 가능하므로 집합과는 다르다. 오른쪽이 하위 bit 이다.) 예를 들어, 0 만 사용된 수라면 0000000001 로 0 번 bit 만 1 이 된다. 1, 4, 9 가 사용되었다면 1000010010 처럼 9번, 4번, 1 번 bit 가 1로 채워진다. 부분 문제를 정의하자. dp[p][x][mask] 는 1. ..

문제 링크 : https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 상담원이 비서를 두고 있다는 사실에 매우 충격을 받은 문제였다. dp 의 정의를 어떻게 하는가는 옳다는 것을 확인하기 전까지는 항상 어렵다. 1. 여기서는 dp[i] 를 ( i-1 ) 번째 일까지 끝난 상담에 대한 금액의 최댓값으로 정의한다. (현실에서는 선불로 받는다 하더라도) 2. dp[i] 은 최소한 dp[i-1] 을 물려받는다. 수익은 기본적으로..

문제 링크 : https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp 문제에서 초기화는 늘 어려운 문제임을 상기시켜 주는 문제. 기본 연속합 문제에 두 가지 추가적으로 고려해야할 사항이 생겼다. 1. 적어도 하나의 수를 선택할 것. (모두 음수로 이루어지 수열의 경우를 주의해야 한다.) 2. 하나를 제거하고 연속합을 만들 수 있다. dp[0][i] = i 를 번째 항으로 끝나는 최대 연속합 으로 정의하자. 이 경우 $$ dp[0][i]= \max( ..

문제 링크 : https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 선행 관계가 작업 번호 순으로 주어지니 딱히 전처리할 것들은 없다. dp[i] 는 i 번째 작업을 마칠 수 있는 최소 시간으로 정의한다. $a[i]$ 를 i 번 작업에 소요되는 시간, $S_i$ 를 i 번 작업에 필요한 선행 작업이라 할 때, 다음 관계식이 성립한다. $$ dp[i]= \max\limits_{j \in S_i } dp[j] + a[i] $$ #include ..

문제 링크 : https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 dp[i-2] 2. i 번 입장..