다이나믹프로그래밍

[백준 2302] 극장 좌석 C++

www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 극장 좌석의 문제는 다이나믹 프로그래밍 문제로, 수열의 규칙을 찾아보면, 피보나치 수열임을 알 수 있습니다. 그 원리를 이용해서 해당 구간의 경우의 수를 곱해주는 문제입니다. 문제에서 VIP좌석이 있지만, 일단 우리는 VIP좌석을 빼고 규칙성을 찾아봅시다. VIP좌석을 빼고 규칙을 찾으면 1부터 N까지의 가능한 경우의 수는 1번째 = 1 2번째 = 2 3번째 = 3 4번째 = 5 5번째 = 8 6번째 = 13 7번째 = 2..

[백준 2533] 사회망 서비스(SNS) C++

www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 백준 사회망 서비스 문제는 트리에서 경우의 수를 구하는 다이나믹 프로그래밍 문제입니다. 서로 연결된 친구들 중에서 얼리아답터가 아닌 노드는 하나 이상의 얼리아답터와 연결되어있어야합니다. 그 때 최소 얼리 아답타를 구하는 문제입니다. 노드 1부터 시작해서 연결되어 있는 모든 노드를 DFS로 찾아가면서 경우수를 만들어주고, Return 하면서 경우의 수를 1만큼 증가 시켜준다음 누적합을 return해주시면 되..

[백준 2169] 로봇 조종하기 C++

www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 이 문제는 1,1에서 시작한 로봇이 N, M까지 도달하는 경로 누적 합 중 최대값을 구하는 문제 입니다. DFS로, 각 공간마다 방향 왼쪽, 아래, 오른쪽으로 나누어서 풀면 되지만, 문제 조건 중에 N, M 제한이 1,000이기 때문에, 매번 갔던 길을 또 계산한다면 시간 복잡도가 어마하게 나올 것으로 생각되었습니다. 다이나믹프로그래밍을 사용해서, 각 지점에서 출발해서 N,M에 도달할 때의 최댓값을 저..

[백준 2096] 내려가기 C++

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 이번 문제는 다이나믹 프로그래밍 문제로, 기존의 다이나믹 문제 유형과 비슷하지만, 메모리를 효율적으로 구성해야하는 문제입니다. 메모리를 효율적으로 사용하기 전에, 기존의 간단한 방법으로 문제를 풀면 배열을 arr[n][3] 배열에서 이전의 위치에서 arr[n][0~3]에 더 해질 수 있는 칸들(arr[n-1][0~3] 중에서 최댓값을 구해서 arr[n][0~3]에 더해주면 됩니다. 문제에서는 별 가능 가능 불가능 이렇게 나와..