백준4 1965번 상자넣기 문제의 해결법 앞에 상자를 넣기 위해서는 뒤에 상자가 앞의 상자보다 더 커야 한다. 최고로 많이 넣을 수 있는 문제를 푼다고 하면, 최장증가부분수열의 문제와 같다고 볼 수 있다. 예제 1번 박스부터 시작하여 1번 박스보다 큰 모든 박스에게 +1해준다. 6번 박스보다 작은 것들은 1번 박스때의 숫자를 가지고 오고 큰 숫자들은 +1이거나 이전 박스까지 센 숫자 중 큰 것을 넣어준다. 점화식 $$dp[i][j] = \begin{cases} max(dp[i][i]+1, dp[i-1][j]), & \text{if }n\text{ box[i] < box[j]} \\ dp[i-1][j], & \text{if }n\text{ box[i]} \ge \text{box[j]} \end{cases} $$ 소스코드 public.. 2021. 5. 19. 동전0 - 11047번 해결방법 알고리즘은 그리디를 사용하였다. 하지만 그리디를 사용해도 최적인지 증명과정이 필요하다. 증명 문제에서는 i개의 동전이 있고, 오름차순으로 주어진다. N을 금액이라고 할 때 동전이 N보다 작다면 항상 아래와 같다. $$ N / C_{i} K >> N; int ans = 0; for (int i = 0; i > c[i]; for (int i = K - 1; i >= 0; --i) if (N >= c[i]) { ans += N / c[i]; N -= (N / c[i] * c[i]); } cout 2019. 4. 29. 동물원 - 1309번 해결방법 O을 배치한 경우, X를 배치 하지 않은 경우라고 할 때 O X | X O | X X 3가지 경우의 수로 둘 수 있다. 그래서 dp를 N * 3개의 배열을 두고 시작하였다. int dp[100001][3] 점화식은 어떻게 될까? 점화식도 3가지로 나눌 수 있다. 만약 O X경우라면 이전의 경우의 수는 X O | X X가 되어야만 하기 때문에 아래와 같아진다. 나머지도 똑같은 방식으로 구해본다면 점화식을 구할 수 있다. $$ dp[i][0] = dp[i-1][1] + dp[i-1][2] $$ $$ dp[i][1] = dp[i-1][0] + dp[i-1][2] $$ $$ dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] $$ 전체코드 #include using n.. 2019. 4. 29. 1102번 - 발전소 해결방법 해당 문제는 bitmask dp로 풀었다. bit가 켜지면 발전소가 켜진 것이고, bit가 꺼지면 발전소가 꺼진 것이다. bitmask dp로 푼 이유는 a번째 발전소가 j번째 가동시킬때와 b번째 발전소가 j번째 발전소를 가동시킬때가 다르기 때문이다. 문제를 풀 때 유의할 점은 0개 이상일 경우이다. 0개 이상일 경우 0을 리턴해야하지 -1를 리턴하게 하면 안된다. int dp[1 > i) % 2 == 1) cnt++; if (cnt >= T) return 0; T보다 작다면 비트가 0인 수를 찾은 다음 비트가 1인 수들 중에서 비용 값을 더해주고 0비트를 1로 바꿔 재귀시켜준다. for (int i = 0; i > i) % 2 == 0) { // 안켜진 발전.. 2019. 4. 19. 이전 1 다음
