1일1알

bfs로 해결할 수 있는 문제이다. 입력을 받은 영역 중에 가장 높은 영역을 max_height 이라고 저장한 뒤, 비가 안오는 경우부터 비가 max_height까지 오는 경우를 모두 검사해서 안전 영역이 제일 많은 경우를 찾았다. 각 지역에 홍수가 났는지를 알려주는 isFlood 2차원 벡터를 만들고 비의 높이에 따라 Init 함수를 통해 isFlood를 초기화 해주었다. 그리고 탐색할 때 visited 배열을 따로 만들기 번거로워서 방문한 안전 영역을 홍수가 난 곳으로 바꿔주면서 탐색을 하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace s..

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. top-down 방식으로 생각해 보면, 우선 예제에서 우리가 찾아야 할 최종 답은 1,2,5 동전을 이용해 10을 만들 수 있는 경우의 수를 찾는 것이다. 이것을 부분적인 문제로 나눠보면, 왼쪽은 5원을 한개 포함시킨 것이다. 5원을 포함시켰지만 또 포함시킬 수 있기 때문에 쓸 수 있는 동전은 같고, 10원에서 5원을 빼서 1,2,5를 사용해서 5원을 만들 수 있는 경우의 문제로 나눴다. 오른쪽은 5원을 포함시키지 않는 경우이다. 그렇기 때문에 1,2를 사용해서 10원을 만들 수 있는 경우의 문제로 나눴다. 여기서 알아낼 수 있는 점화식은 dp[i][j] = dp[i][j - v[i]] + dp[i-1][j] 이다. (v는 동전의 가치의 배열) 하지만 j..

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. dp 테이블을 보면서 설명을 해보자면, 우선 행은 숫자의 길이이고 열은 맨 앞의 숫자이다. 문제에도 나와있듯이 숫자는 0으로 시작할 수 있다. 길이가 0개인 숫자는 없으니 0행은 모두 0이고, 길이가 1개인 숫자는 맨 앞 숫자가 무엇이든 1개이니 1행은 모두 1이다. 2행부터 살펴보자면, 우선 시작 숫자가 9이면 가능한 숫자는 99 하나밖에 없다. 그래서 9열은 우선 1로 채워준다. 그 다음부터는, 예를들어 7열을 보면 77,78,79가 가능한데, 이것을 1행과 연관지어서 생각해보면 1행의 7,8,9열은 길이가 1이고 시작하는 숫자가 7,8,9인 숫자들이기 때문에 당연히 7 뒤에 붙어셔 2자리 오르막 수로 만들 수 있다. 그래서 2행의 7열은 1행의 7,..

한정된 공간 안에 최대한의 가치를 넣는 배낭 채우기와 비슷한 문제이다. 카드의 개수가 무게, 가격을 가치라고 생각하면 된다. 하지만 한가지 다른 점이 있는데, 한 종류의 카드팩을 여러번 살 수 있다는 것이다. 점화식을 세우기 위한 과정을 우선 top-down 방식으로 생각해 보면 이런 식으로 그려볼 수 있다. 설명을 해보자면, 루트는 우리가 최종 구해야 할 답이고, N개의 카드를 최대한의 가격으로 구매할 때의 가격이다. 왼쪽으로 나눠진 부분은 4번 카드팩을 구매했을때의 상태이다. 4번 카드팩을 구매해서 카드의 개수가 4만큼 줄어들어서 0이 되었고, 카드팩은 구매했다고 사라지는게 아니기 때문에 사용가능한 카드팩은 그대로인 모습이다. 그리고 구매한 카드팩의 가격을 더해준 것이다. 오른쪽으로 나눠진 부분은 4..

파이프를 오른쪽으로 옮길 때에는 현재 위치에서 오른쪽 한 칸이 비어있어야 하고 아래로 옮길 때에는 아래에 한 칸이 비어있어야 한다. 대각선으로 옮길 때에 주의해야할 점이 있는데, 대각선으로 간 칸과, 그 위칸과 왼쪽 칸 모두 비어있어야 한다는 것이다. 문제에도 비어있어야 할 칸이 색으로 칠해져있다. 나는 구조체를 만들어서 파이프의 위치와 현재 상태(오른쪽, 대각선, 아래 중 하나) 정보를 저장하고 그 구조체를 큐에 넣어서 bfs방식으로 해결하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; str..

간단한 브루트포스 문제이다. 모든 칸을 돌면서 오른쪽, 아래쪽으로만 검사하면서 정사각형이 되는지 확인하고 크기가 커질때마다 크기를 갱신해주었다. #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); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; string str; vector v(n, vector(m)); for (int i = 0; i >..