백준 12177번 Dreary Design - C++(cpp) 풀이
1. G-R과 B-G를 고정한다. 2. R, G, B 값이 모두 0 이상 K이하가 되도록 하는 R 값을 모두 구한다. 3. 가능한 모든 (G-R, B-G) 쌍에 대해 1,2를 반복한다. 1. G-R과 B-G를 고정한다. K 범위가 굉장히 크기 때문에 K 대신 V를 기준으로 생각해준다. 결국 R, G, B 값의 차를 모두 V 이하로 만들어야 한다. G-R 값과 B-G 값을 정하고 나면, R값만 정해도 G, B 값이 저절로 정해진다. 2. R, G, B 값이 모두 0 이상 K이하가 되도록 하는 R 값을 모두 구한다. 1에서 고정한 값을 G-R = i, B-G = j 라고 하자. 이를 가지고 G와 B를 나타내면, G = R+i, B = R+i+j 이다. R, G, B 값이 모두 0 이상 K 이하여야 하므로, ..
2022. 3. 22.
백준 12969번 ABC - C++(cpp) 풀이
1. 오름차순 쌍이 K개인 문자열 S 앞에 어떠한 문자 X를 붙여 문자열 XS를 만들었을 때, 문자열 XS가 가진 오름차순 쌍의 수는 K + (S에 포함된 X보다 큰 문자의 수)이다. 2. dp(a, b, c, k) = 'A', 'B', 'C'를 각각 a, b, c개 가지고 있으면서 오름차순 쌍이 k개인 문자열의 존재 여부 3. 따라서 'A'로 시작하는 경우, 'B'로 시작하는 경우, 'C'로 시작하는 경우를 모두 고려하면, dp(a, b, c, k) = dp(a-1, b, c, k-b-c) 또는 dp(a, b-1, c, k-c) 또는 dp(a, b, c-1, k) 1. 오름차순 쌍이 K개인 문자열 S 앞에 어떠한 문자 X를 붙여 문자열 XS를 만들었을 때, 문자열 XS가 가진 오름차순 쌍의 수는 K +..
2022. 3. 20.
