enopid 님의 블로그

https://www.acmicpc.net/problem/17234문제 분석 문제는 0점부터 시작하여 3가지 선택을 반복하며, $($1. 점수에 a점 추가  2. 점수에 b점 추가 3. 점수를 2배$)$두 가지 조건을 만족시키며 $($1. 점수가 N+a 미만 2. 2배 한 횟수가 전체의 10% 이하$)$가장 빨리 N에 도달하는 문제이다. 기본적으로 점수, 턴 수, 2배 횟수 총 3가지를 고려해야 하므로 시간복잡도 $N^3$의 DP 문제로 하면 복잡도가 1억이 초과하여 불가능해 보인다.$($안 해봐서 모른다 의외로 될지도 굉장히 애매한 복잡도$)$ 하지만, N이 500 이하이므로 2배를 수행하는 선택이 10번 이상 나오면 값이 최소 1024$(=2^{10})$이므로 10번 이상의 2번 연산은 배제하면 되어..

https://www.acmicpc.net/problem/15166문제 분석 서로 같이 싣을 수 없는 약들을 고려했을 때, 좌우 화물의 무게 제한을 넘기지 않고 약을 싣을 수 있는지를 묻는 문제이다. 이를 해결하기 위해서 문제를 두 가지 조건으로 나누어 접근해야 한다.1. 무게를 고려하지 않았을 때 두 개로 나누는 것만으로 같이 싣으면 안 되는 약끼리 분리가 되는지ex) (1,2), (2,0), (0,1) 같이 있을 수 없는 쌍이라면 애초에 두 개만으로 는 분리가 불가능하다.2.  1번 조건을 만족한다면 좌우 무게까지 고려해서 두 개로 분리 가능 한지 1번째 조건에 대한 해결은 DFS로 사용하며 매깊이마다 달라지는 플래그를 사용해서  해결가능하다. 우선, 같이 싣으면 안 되는 쌍이 입력으로 들어왔을때 이..

https://www.acmicpc.net/problem/21636문제 분석 문제는 n과 k가 주어졌을 때 합이 N이 되게끔 숫자를 분할하고 각 숫자별로 k개의 색 중 하나를 배정했을 때 나올 수 있는 경우의 수를 구하는 문제이다. 단순히 합이 N이 되게끔 숫자를 분할하고 각 숫자별 개수에 따라 k개의 색을 배분하는 케이스를 구하면 된다. 합이 N이 되는 숫자의 조합은 단순히 DP를 통해서 조합의 수는 구할 수있지만 실제 각 숫자별 개수가 필요하여 다른 방식을 사용해야 한다. 브루트 포스로 모든 케이스를 고려하여 구해도 된다. N은 최대 17이므로 분할가능한 케이스는 순서를 고려해도 $2^{16} \approx 64000$의 크기를 가진다. 다만, 중복을 제거해야 하므로 백트래킹 방식을 사용하여 가장 큰..

https://www.acmicpc.net/problem/9472문제 분석 우선 인자의 범위를 분석했을 때, N이 [1,17]의 범위를 가지고 K는 [0, N]의 범위를 가지므로 가능한 S(n, k)는 18*18의 비교적 적은 가지 수로 볼 수 있다. 따라서, 테스트케이스의 수가 적지 않은 이상 각 테스트 케이스를 처음부터 계산하는 방식보다는 18*18 사이즈의 S(n, k) 테이블을 미리 계산하는 방식이 더 효과적이라고 생각했다.  본 문제에서 S(n,k)는 N개의 이분매칭 문제에서 적어도 위에서부터 K개를 틀리는 경우의 수를 의미한다. S(n, k)를 바로 구하고자 할 때 k개 이후는 맞고 틀리고 여부를 판별하지 않아 단순 (n-k)! 의 조합이지만  문제는 앞선 K개의 조합의 수이다. 정답 여부까지..