목록다이나믹 프로그래밍 (63)

1일1알

백준 17070번 파이프 옮기기 1 C++

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

dp 테이블을 이용하여 누적 합을 저장해서 풀 수 있는 문제이다. 예제의 숫자들을 각 행마다 누적 합을 저장하여 저장한다. (2,2)부터 (3,4) 까지의 합은 이 부분의 합을 구하면 되기 때문에 dp[2][4]-dp[2][2-1] + dp[3][4]-dp[3][2-1] = (14 - 2) + (18 - 3) = 27 이렇게 구할 수 있다. 이것을 코드로 나타내면 #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...
알고리즘 2021. 10. 18. 13:19
백준 9465번 스티커 C++

다이나믹 프로그래밍 bottom-up 방식으로 풀 수 있는 문제이다. 우선 두 가지 경우가 있다. 1. 왼쪽 위에서 시작하는 경우 2. 왼쪽 아래에서 시작하는 경우 1번의 경우를 예를 들어 살펴보면 한 칸 떨어진 대각선을 선택하는 경우와 두 칸 떨어진 대각선을 선택하는 경우로 나눌 수 있다. 다른 어떤 곳을 선택하더라도 결국 이 두 가지로 나뉜다. (100을 선택: 50->50->100, 20을 선택: 50->50->20 or 50->70->20, 10을 선택: 50->50->100->10) 위 경우들을 살펴보면 결국 위의 두 가지의 경우들의 조합으로 만든 선택임을 알 수 있다. 마지막 스티커까지 도달했을 때 1번의 경우와 2번의 경우 중 큰 값이 답이 된다. max(dp[0][n], dp[1][n]) ..
알고리즘 2021. 10. 16. 13:09
이전 Prev 1 ··· 8 9 10 11 Next 다음