비트마스크 (5) 썸네일형 리스트형 타일 채우기 문제를 푸는 테크닉 1 이 게시글에서는 타일을 채우는 것과 관련한 문제에서 특수한 경우에 사용하는 기술을 알아본다. N * M 크기 격자의 상태를 정수 한 개로 표현하기 https://atcoder.jp/contests/abc196/tasks/abc196_d D - Hanjo AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 길이가 1, 2인 블럭으로 H * W 크기의 격자를 채우는 가짓수를 출력하는 문제이다. 이 문제는 $HW \leq 16$이라는 조건과 이러한 타일링 문제에 적용되는 성질로 인해 재미있는 생각을 떠올릴 수 있다. 1. 어떤 행.. 백준 1086 - 박성원 icpc.me/1086 푸는 방법을 고민하기 전에... 어떤 큰 정수를 100 이하의 수로 나눈 나머지를 구하는 것은 어렵지 않다. 나눗셈을 손으로 푸는 과정을 구현하면 된다. 큰 정수를 스트링으로 받은 다음 반복문을 통해 (이전 자릿수까지 나눗셈을 통해 나온 나머지 * 10 + 현재 자릿수) % K 하면 된다. C계열 코드로는 다음과 같이 쓸 수 있겠다. 1 2 3 4 int pre = 0; for (int j = 0; j > k; for (int i = 0; i 백준 1480 - 보석 모으기 icpc.me/1480 솔루션 - 이차원 DP 더보기 테이블을 다음과 같이 정의한다. dp[i][j] := i번째 가방까지 보석의 조합을 비트마스크로 표현한 j로 채우는게 가능한가? 첫번째 가방에 보석을 채울 수 있는 경우를 비트마스크로 확인하고 다음 가방에 다른 보석을 넣는 경우를 계산한 후 m번째 가방까지 썼을 때 최대 비트를 구해 출력하면 된다. 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68.. [KOI] 백준 2666 - 벽장문의 이동 icpc.me/2666 문제 이해와 그 접근 어떤 벽장을 사용하려는데 열려있다면 추가 비용 없이 그대로 이용할 수 있다. 만약 닫혀있다면 사용을 위해 벽장문을 밀어야 하는데 초기에 열린 벽장이 두개 주어지므로 닫혀있는 벽장을 열 수 없는 경우는 없다. 증명은 생략. 그렇다면 벽장문을 미는 경우는 두개로 나뉘어진다. 왼쪽으로 밀던가 오른쪽으로 밀던가. 동적계획법을 통해 이 두가지의 경우를 적절히 탐색하여 최소 비용을 찾아내면 될 것이다. 구현 dp 테이블을 이차원으로 구성했다. dp[i][j] := i번째 벽장을 열려고 하고 벽장이 j와 같은 상태일 때(비트마스크) 최소 비용 탑다운 dp를 통해 왼쪽으로 미는 비용과 오른쪽으로 미는 비용을 비교해서 최솟값을 구하면 된다. 각 방향마다 벽장문을 몇개 밀어야 .. 백준 3980 - 선발 명단 www.acmicpc.net/problem/3980 3980번: 선발 명단 문제 챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다. 오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었� www.acmicpc.net 11명의 선수를 배치했을 때 최대 능력치를 구하는 문제이다. 11명을 전부 배치할 수 있는 TC만 주어지며 반드시 11명을 배치해야 한다는 점을 주의하자. 11명을 반드시 배치해야 한다는 조건에 주목하여 비트마스크 DP, 탐색 등의 방법을 통해 능력치의 최댓값을 찾도록 한다. 단, 비트마스크 DP를 이용시 다음과 같은 케이스에 유의하도록 한다. 1 10 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0.. 이전 1 다음
