1일1알

직사각형의 경로에서 동그라미가 주어지면 그 곳을 거쳐서 오른쪽 밑 끝까지 가고, 주어지지 않으면 그냥 오른쪽 밑 끝까지 가는 경우의 수를 구하는 문제이다. 동그라미의 좌표가 주어지지 않으면 (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 ..

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 3가지 경우가 있는데, 사자를 배치하지 않는 경우, 왼쪽에 배치하는 경우, 오른쪽에 배치하는 경우가 있다. dp[n][3] 의 dp테이블을 만들어서 0열에는 배치하지 않을 때의 경우의 수, 1열에는 왼쪽에 배치할 때의 경우의 수, 2열에는 오른쪽에 배치할 때의 경우의 수를 넣어서 문제를 해결할 수 있다. 우선 우리의 크기가 1일 때에는 dp[1][0] = 1, dp[1][1] = 1, dp[1][2] =1 로 모두 하나의 경우의 수를 가진다. 다음 우리의 크기가 2일 때에는 사자를 배치하지 않는 경우는 위의 세 가지 경우 모두 가능하기 때문에 dp[2][0]=dp[1][0]+dp[1][1]+dp[1][2] 이다. 사자를 왼쪽에 배치하는 경우는 1행에서 사..

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 우리가 원하는 답은 1, 5, 12원의 동전으로 15원을 만들 때 가장 적게 드는 개수를 찾는것이다. 최종 답에서 top - down 방식으로 우선 생각해볼 때 두 가지 경우로 나눌 수 있다. 첫번째는 맨 뒤에 있는 12원의 동전을 포함한 경우이다. 이 경우는 같은 동전을 여러번 사용할 수 있으므로 1, 5, 12원으로 3원을 만드는 작은 문제로 나눌 수 있다. 이때는 12원의 동전을 하나 선택했기 때문에 +1을 해줘야한다. 두 번째는 12원의 동전을 포함하지 않은 경우이다. 이 경우는 1, 5원으로 15원을 만드는 작은 문제로 나눌 수 있다. 이 중 작은 값이 답이 되고, 나눠진 문제에서 같은 방식으로 또 나누면서 문제를 해결할 수 있다. 이 방식으로 ..

간단한 dp 문제이다. (r, c)에서의 사탕의 최대값은 (r - 1, c) , (r, c - 1), (r - 1, c - 1) 중 누적된 사탕의 개수가 가장 큰 값에 현재 위치의 사탕의 수를 더하면 된다. 여기서 만들 수 있는 점화식은 dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + v[i][j] 이다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); c..

단순한 dp문제처럼 보이지만 조금 생각해봐야 할 것이 있는 문제이다. 우선 3*2 타일은 이렇게 세 가지가 가능하고, 1*2와 2*1 타일만 사용하기 때문에 타일의 면적은 무조건 짝수가 나온다. 그러므로 3*홀수의 타일은 불가능하다는 것을 알 수 있다. 3*3 타일은 불가능하기 때문에, 3*4 타일의 경우를 생각해보면, 일단 3*2 타일의 경우에서 각각의 타일에 3*2타일을 또 붙이는 경우 일단 이렇게 9가지가 있고, 새로운 모양이 나온다. 이런 모양이 나오는데, 위아래로 뒤집어서 이런 모양이 2개가 나온다. 그래서 3*4 타일의 개수는 11개이다. 이제 3*6 타일을 살펴보면, 우선 이런 경우가 있다. 2칸 전의 타일에서 3가지 방법을 추가하는 경우 (dp[i-2]*3) 그리고 4칸 전부터 새로운 모양..

bfs로 해결할 수 있는 문제이다. 처음에 좌표의 시작점이 왼쪽 아래 (0, 0) 이라 조금 헷갈렸지만 그냥 배열처럼 왼쪽 위 (0, 0)에서 시작해도 결과는 같다. 모양은 위아래로 뒤집어진 모양이 나오지만 영역의 개수와 넓이에는 변화가 없을 것이니 그렇게 해결하기로 했다. 두 번째 줄부터 x1, y1, x2, y2의 좌표가 주어지는데, x는 열, y는 행의 좌표이기 때문에 row1 = y1 col1 = x1 row2 = y2 col2 = x2 라고 저장한 뒤 이 좌표로 둘러싸인 직사각형의 공간을 채워졌다고 표시하고, bfs방식으로 해결하였다. visited 배열을 만들기 귀찮아서 방문한 좌표는 채워졌다고 변경하면서 탐색하였다. 직사각형을 돌면서 채워지지 않은 곳을 발견하면 cnt를 올리고 size를 1..