DP8 [C++] 백준 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 행의 크기가 2, 열의 크기가 n인 입력이 주어졌을 때 상,하,좌,우로 이웃하지 않는 숫자를 더해 만들 수 있는 최대합을 구하는 문제입니다. 숫자를 선택하는 점화식을 찾아 bottom-up방식의 다이나믹 프로그래밍을 사용해 문제를 해결할 수 있습니다. dp[i][j]에는 i, j 에서의 최대합을 저장해야 합니다. 최종 j에 도달한 후에는 dp[0][j]와 dp[1][j] 중 최대값.. 2024. 1. 22. [C++] 프로그래머스 2 x n 타일링 https://school.programmers.co.kr/learn/courses/30/lessons/12900 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 Dynamic Programming 을 사용해 풀이하는 문제입니다. 어려워 보이지만 점화식만 잘 찾는다면 쉽게 해결할 수 있습니다. #include #include using namespace std; int dp[60001]; int solution(int n) { int answer = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; dp[4] = 5; if (n > 4).. 2023. 11. 5. [C++] 백준 17626 Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 풀이 임의의 자연수를 만드는데 필요한 제곱수의 최소 개수를 저장하는 DP를 사용해 풀이하면 된다. 1. 모든 자연수는 넷 혹은 그 이하의 제곱수 합으로 표현할 수 있다. 2. 예시 n 1 2 3 4 5 6 7 8 을 표현하면 dp[n] 1 2 3 1 2 3 4 2 이다. 3. 임의의 자연수에서 제곱수를 뺏을 때, dp[n]이 최소값을 가지는 숫자에서 해당 자연수.. 2023. 1. 31. [C++] 백준 1520 내리막길 [Gold3] https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 1. 내리막길로만 이동하여 M, N 에 도달하는 경로의 수를 찾는 문제이다. 2. 단순하게 DFS 돌려봤으나 역시나 시간초과로 실패했다. 3. DFS + DP 방법과 우선순위 큐를 사용한 BFS 알고리즘으로 문제를 해결할 수 있다. 알고리즘: DFS + DP 1. dp[row][col] 에 저장 할 값은 M, N 에 도달하는 경로의 가지 수 이다. 2. dp[row][col] 을 -1로 초.. 2023. 1. 21. [C++] 백준 2294 동전 2 DP 풀이 1. DP[n] 에 저장하는 값은 n을 만들때 필요한 최소 동전 개수이다. 2. 최소 동전 개수를 구하므로 DP 벡터를 10001로 초기화 하고 최소 값을 찾는 점화식을 돌리면 된다. 3. 점화식은 n을 만들기 위해 dp[n-현재동전] 에 저장된 최소 동전 개수에 +1을 해주면 현재동전을 사용하면서 n을 만드는 경우이다. 4. DP[0] = 0으로 초기화하여 시작하면, 현재동전이 2일 때 DP[2] = DP[2-2] +1 과 같은 경우에 1을 얻을 수 있다. 이때 1을 사용해 2를 만드는 동전 개수 2보다 1이 작으므로 DP[2] = 1 로 업데이트 된다. DP[4] = DP[4-2]+1 = 2 로, 기존의 1을 사용해 4를 만들때 동전 개수 4보다 작으므로, 동전을 중복으로 사용하면서 업데이트 할.. 2023. 1. 16. [C++] 백준 2293 동전 1 DP 풀이 예시: 1,2,5를 사용해 10 만들기, 단 중복집합x 1. 먼저, 1을 사용해 x원을 만들 때 가능한 경우는 모두 1가지 뿐이다. DP표에 각 수를 만들 수 있는 경우의 수를 저장한다. 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 2. 2를 사용하는 경우를 따져보자. x원을 만든다고 했을 때, 2를 사용해 x를 만드려면 이전 값은 x-2 이어야 한다. 단순히 x-2에 2를 추가해주면 x가 만들어진다. 2를 사용해 2을 만드는 방법은 한 가지. 그럼 2를 사용해 3을 만드는 경우는? 1원을 만드는 모든 경우의 수에서 2원을 추가해주면 된다. 따라서 1원을 만드는 모든 경우의 수인 1가지이다. (1 + 2 = 3) 그렇다면 이때, 1원과 2원을 사용해서 3을 만드는 모든 .. 2023. 1. 16. [C++] 백준 11726 2xn 타일링 DP 풀이 1. 전체 타일은 가로축으로만 늘어난다. 2. 전체 타일이 2x3 일때 가능한 경우는 =, ll 이다. 3. 전체 타일이 2x3 일때 가능한 경우는 =l, l=, lll 이다. 4. 타일을 붙이는 경우는 l 또는 = 인데, 타일이 하나 늘어날 경우 l을 붙이거나 하나 줄인 상태에서 =를 붙이는 경우가 가능하다. -> l를 붙이는 것은 n-1의 모든 경우의 수에 대해 가능하다. 또한 =를 붙이는 것도 n-2 모든 경우의 수에 가능하다. 5. 따라서 n에서 가능한 경우는 n-2 경우의 수와 n-1 경우의 수의 합이다. (dp[n] = dp[n-2] + dp[n-1]) 리뷰 nx2를 nxn으로 착각해서 점화식을 어떻게 세우나 한참 고민했다. 문제를 잘 읽자. #include #include #includ.. 2023. 1. 16. [C++] 백준 2839 설탕배달 DP 풀이 1. DP를 활용해서 해결했다. 2. 타겟 값이 9라고 할 때 3과 5를 사용해서 9를 만들기 위해서는 직전 값이 6 또는 5만 가능하다. 3. 이때 dp[5], dp[6]에 저장된 값은 5, 6을 만들기 위해 최소로 필요한 봉지 개수이다. 3. 따라서 점화식, dp[n] = min(dp[n-3], dp[n-5])+1 을 세울 수 있다. 4. 추가로 dp[x] = 0 인 부분은 3과 5로 만들 수 없는 값이므로 조건문으로 배제하면 된다. 나는 3번의 if문을 통해서 해결했다. dp[i-3]이 있다면 업데이트, dp[i-5]가 있다면 업데이트, dp[i-3], dp[i-5] 둘다 있으면 최소값에 대해 업데이트 한다. 리뷰 dp를 선언할 때 벡터로 선언하냐, 배열로 선언하냐에 따라 메모리 초과가 떳다... 2023. 1. 16. 이전 1 다음