실버 I3 [11502] 카드 구매하기 - c++ https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 정후이 폼 미쳐 따이.... 드디어... 드디어 내 혼자 힘으로 DP 문제를 풀어 버렸다... 이게 무슨 일인고 풀고 난 후에 다른 사람들 풀이를 봤을 때 좀 이상하게 푼 감이 있지만 일단 풀이를 시작하겠다! 아이디어 최근에 KnapSack문제가 인상 깊어서 그런가? 이 문제도 비슷하게 풀 수 있을 것 같았다. DP테이블을 이차원으로 정의 행(row) => i번째 카드 번호 열(column) => j개의.. 2023. 6. 19. [2302] 극장좌석 - c++ https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 정말 미세하게 DP에 대한 감이 잡히기 시작한 것 같다. DP문제라는 것을 알고 풀긴 했지만! 점화식을 찾아냈다는 것이 뿌듯했다. 하지만 점화식을 찾아낸 것 그뿐이고 그다음을 어떻게 해야 할지 몰라 답을 찾아서 봤다....ㅎ 풀이 먼저 점화식을 찾아낸 방법은 하나하나 다 써봤다. 이것만큼 좋은 게 있을까? $$\Large d[i] \space =\space d[i-1] \space + \space d[i-2].. 2023. 6. 17. 1932 - c++ https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 시행 착오 최근에 다이나믹 프로그래밍 문제를 풀때 테이블이나 재귀식이 새각나지 않는 다면 브루트 포스 또는 모든 것을 다 검사하는 방식으로 코드를 짜보고 거기서 추가 적으로 재귀를 짜라는 식의 설명을 들은 적이 있다. 그리하여 나는 일단 DFS를 사용하여 모든 경우의 수를 다 구하였으며, 결과는 시간 초과 였으며 당연한 결과라 생각해 다이내믹 프로그래밍으로 짜보려고 노력했다. CODE #include using namespace std; void init(){ ios_.. 2023. 6. 4. 이전 1 다음
