목록전체 글 (616)

1일1알

백준 11048번 이동하기 C++

간단한 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..
알고리즘 2021. 10. 29. 10:53
백준 2133번 타일 채우기 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칸 전부터 새로운 모양..
알고리즘 2021. 10. 28. 12:38
백준 2583번 영역 구하기 C++

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

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

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 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..
알고리즘 2021. 10. 25. 12:35
백준 11057번 오르막 수 C++

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 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,..
알고리즘 2021. 10. 24. 11:33
이전 Prev 1 ··· 98 99 100 101 102 103 Next 다음