DP (3) 썸네일형 리스트형 [BeakJoon 1480] 보석 모으기 안녕하세요. 이번 포스팅에서는 백준 1480 보석 모으기 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/1480 1480번: 보석 모으기 첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C가 주어진다. N은 1보다 크거나 같고, 13보다 작거나 같은 자연수이고, M은 1보다 크거나 같고, 10보다 작거나 같은 자연수이다. C는 1보 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 처음 이 문제를 보았을 때 각 가방의 한도가 같기 때문에 투 포인터 형식으로 접근을 하였는데, 해당 방식이 최적해를 구하지 못합니다. 따라서 이 문제는 Dynamic Programming으로 모든 status에 대한 검사를 해야 합니다. 가방의.. [BeakJoon 17623] 괄호 안녕하세요. 이번 포스팅에서는 백준 17623 괄호 문제를 풀어보도록 하겠습니다. 문제는 https://www.acmicpc.net/problem/17623 17623번: 괄호 6개의 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 로 이루어진 올바른 괄호 문자열 W에 대하여 정수의 ‘괄호값’을 지정하는 함수 val(W)가 정의되어 있다. 먼저 올바른 괄호 문자열부터 정의해 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 이 문제를 dynamic programming으로 접근해서 해결하였는데, dmap값을 기준으로 dp[n] -> val(x)=n인 x 중 최솟값으로 갱신하였습니다. 조금 더 풀어서 점화식으로 설명하자면, dp[1] = "()" dp[2] = "{}" dp[3] =.. [BeakJoon 17070] 파이프 옮기기1 안녕하세요. 이번 포스팅에서는 백준 17070 파이프 옮기기1을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 이 문제는 분류상 DP긴 한데, 저는 이 문제의 경우 역행하는 경우의 수도 없고, 고려해야할 경우의 수도 최대 16x16x7이기 때문에 BFS로 풀었습니다. #include using namespace std; int n, res, board[17][17]; const int dir[3.. 이전 1 다음
