1일1알

조금 특이한? dp 문제이다. 우선 점화식을 세울 때 생각한 것은 어떤 날이든 첫째 날과 둘째 날의 떡의 개수로 분해할 수 있다는 것이다. 예를 들어 5번째 날은 3번째 날 + 4번째 날이고, 3번째 날은 1번째 날 + 2번째 날, 4번째 날은 2번째 날 + 3번째 날.. 이런 식으로 밑으로 내려가면서 최종적으론 1번째 날과 2번째 날의 떡의 개수의 조합으로 나타낼 수 있다. 그림으로 나타내면 이런 식으로, 5번째 날은 최종적으로 2 * 1번째 날, 3* 2번째 날의 떡의 개수로 나타낼 수 있다. 하지만 숫자가 주어질 때마다 이런 식으로 계속 분해하면 시간이 오래 걸리기 때문에 bottom-up 방식으로 해결하기로 생각했다. pair을 이용하여 dp배열을 만들었는데, 첫 번째 원소는 첫 번째 날 떡의 개..

직사각형의 경로에서 동그라미가 주어지면 그 곳을 거쳐서 오른쪽 밑 끝까지 가고, 주어지지 않으면 그냥 오른쪽 밑 끝까지 가는 경우의 수를 구하는 문제이다. 동그라미의 좌표가 주어지지 않으면 (0, 0)에서 (n-1, m-1) 까지의 경우의 수를 구하고 동그라미의 좌표가 (x, y)라고 주어지면 (0, 0)에서 (x, y) 경우의 수와 (x, y,)에서 (n-1, m-1)까지의 경우의 수를 곱하면 된다. 동그라미는 좌표가 아닌 숫자로 주어지기 때문에 좌표로 변환해야 한다. 숫자가 k로 주어지면 ( (k - 1) / m , (k - 1) % m ) 의 식을 통해 좌표를 구할 수 있다. bfs방식을 통해서 경우의 수를 구하였다. #include #include #include #include #include ..

#include #include #include #include #include #include #include using namespace std; int main() { int a, b, c; int arr[3]; while (1) { cin >> a >> b >> c; //while문 종료 if (a == 0 && b == 0 && c == 0) break; arr[0] = a; arr[1] = b; arr[2] = c; //오름차순 정렬 sort(arr, arr + 3); if (arr[0] * arr[0] + arr[1] * arr[1] == arr[2] * arr[2]) { cout

#include #include #include #include #include #include using namespace std; int main() { int x, y, w, h; int min = 1001; cin >> x >> y >> w >> h; //x좌표 비교 (0에서 x까지의 거리와 w에서 x까지의 거리) if (x > w - x) { if (w - x h - y) { if (h - y < min) { min = h - y; } } else { if (y < min) { min = y; } } //네 개의..