이동식 저장소

특별히 이번 글은 내가 배운 내용을 적으려 한다. 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼�� www.acmicpc.net 보자마자 DP로 풀면 되겠다는 생각이 들었다. 그런데 dp 정의를 생각하기가 너무나 어려웠다. 분명 $dp[i][j][k]$ 꼴이어야 하는데, $l$과 $r$은 당연하지만 $i$를 무엇으로 정의해야 할지 고민이었다. 빌딩의 총 개수로 놓으면 말이 안 되고. 그래서 1328번은 검색으로 풀었다. 검색한 결과 $i$는 가장 높은 빌딩의 높이로 정의해야 한다. $dp[i][j][k]$는 최고 높이가 $i-1$인 상..

예전부터 북마크만 해놓던 문제. 한 두달 됐나? 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 10844. 쉬운 계단 수를 강화한 문제이다. 10844번에서는 아주 간단한 2차원 DP로 풀 수 있었다. 다음과 같이 정의하면 된다. $dp[i][j]$: 길이가 $i$이고 $j$로 끝나는 계단 수의 개수 그런데 1562번 문제에서는 0부터 9까지의 숫자가 적어도 한 번 등장해야 한다는 조건이 있다. DP를 이렇게 정의해 보자. $dp[i][j][k]$: 길이가 $i$이고 $j$로 끝나며, 비트마스크가 $k$인 계단 수의 개수 여기서 $k$는 10자리의 비트마스크이다. 어떤 수에 $i$가 들어 있다면 $k\&(1

7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블� www.acmicpc.net $N$개의 기계가 일렬로 배치되어 있다. 기계의 배열에서 케이블이 교차하는 횟수를 세야 한다. 우선 문제를 간단하게 모델링하자. 식별 번호 대신 1부터 시작하는 인덱스를 부여하고, $pos[i]$를 A열의 $i$번째 기계가 연결된 B열의 기계의 위치로 정의하자. 예제 1을 예로 들면 $pos$ 배열은 다음과 같다. 3 1 4 2 5 케이블이 꼬여 있다는 것은 두 케이블의 상대적인 방향이 다르다는 뜻이다. 이 조건은 $i pos[j]$라는 식으로 표현할 수 ..

최근 팀플땜에 바빠서.. 오랜만에 문제를 풀어 보았다. 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 구멍이 $N$개인 멀티탭이 있고, $K$종류의 전자제품이 있다. 전자제품을 주어진 순서대로 총 $K$번 사용하려 할 때, 멀티탭에 꽂혀 있던 플러그를 최소한 몇 번 뽑아야 하는지 계산해야 한다. 문제를 읽자마자 그리디라는 감이 왔다. 1. 멀티탭에 빈 플러그가 있다면 그냥 꽂으면 된다. 2. 사용하려는 전자제품이 이미 꽂혀 있으면 그냥 넘어가면 된다. 3. 멀티탭에 새로 꽂아야 하는데 빈 플러그가 없는 경우..

1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 이 문제는 Croatian Open Competition in Informatics 2013-2014 Contest #1에서 사용된 문제이다. 대회에서 사용된 입력이 공개되어 있으니 제출하기 전에 테스트해 보자. 압축을 풀어서 lopov를 찾으면 된다. 훔친 보석의 가격의 합을 최대로 하게끔 보석을 가방에 담는 문제이다. 대충 생각해 보면, 보석 가격이 큰 것부터 훔쳐야 할 것 같다. 이 문제는 냅색도..