DP52 [leetcode] 1155. Number of Dice Rolls With Target Sum 문제 : https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/ DP 문제. int dp[d+1][target+1]; // dp[d][sum] = d개의 dice로 sum을 만들 수 있는 경우의 수 점화식은 위와 같다. 먼저 dp[1][1~target]을 1로 초기화 시킨다. (다이스 1개로 만들 수 있는 경우의 수 세팅) dp 배열을 행우선탐색으로 탐색하면서 배열을 채운다. (dice, sum) dp 요소를 채운다고 할 때, for(int face=1; face 2019. 9. 8. [codeground] 8. 블럭 없애기 codeground - Practice - 연습문제 - 8. 블럭 없애기 문제 : https://www.codeground.org/practice/practiceProblemList 1. i번째 블럭 높이(h) a h b -> 높이가 h인 블럭 없어지는데 걸리는 시간 = h 2. i번째 블럭(h)의 양쪽 블럭이 없어지는데 걸리는 시간 중 최소값 + 1 a h b -> 높이가 h인 블럭 없어지는데 걸리는 시간 = (a, b 중 작은 값) + 1 i번째 블럭이 없어질 때까지 걸리는 시간은 1, 2번 중 최소값이다. int d[n + 2];//d[i] = i번째 블럭이 없어질 때까지 걸리는 시간 즉, d[i] = min(d[i-1] + 1 , d[i+1] + 1, i번 블럭 높이) i 번째 블럭이 모두 없어지.. 2019. 9. 2. 외판원 순회(TSP: Traveling Salesperson Problem) 외판원 순회(TSP: Traveling Salesperson Problem)란 도시들이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다. 외판원 순회는 NP문제로 이번에 소개할 알고리즘은 N이 16개 이하일 때 DP와 비트마스크를 이용하여 구하는 방법입니다. DP는 특정 도시들을 방문한 상태일 때 최소 비용을 저장해 놓고 이를 사용합니다. 비트마스크는 특정 도시를 방문한 상태를 저장할 때 사용합니다. 예를 들어서 1~3번 도시가 있다고 했을 때, 110(2)는 2,3번 도시를 방문한 상태입니다. 110(2)를 십진수로 바꿔보면 6(1x22 + 1x21 + 0x20)이 됩니다. 즉,.. 2019. 8. 31. [codeground] 36. 재활용 codeground - Practice - SCPC 2회 본선 - 36. 재활용 문제 : https://www.codeground.org/practice/practiceProblemList vector arr; //arr[i] : i집의 x위치 vector sum; //sum[i] : 1~i 집들의 x위치 합 int d[501][501]; //d[s][k] : s~n 까지의 집이 k개의 수집통에 재활용을 넣는 경우 드는 최소 비용 int go(int s, int k) //d[s][k] 채우는 함수 일단 x좌표에 대해 오름차순 정렬해준다. 이제 d배열을 채워보자. 만약 a~e 집이 1개의 재활용 수집통을 사용한다고 했을 때, 가장 적절한 수집통의 위치는 어디가 될까. 가장 적절한 수집통의 위치를 x라고 했.. 2019. 6. 12. [algospot][ASYMTILING] 비대칭 타일링 문제 : https://algospot.com/judge/problem/read/ASYMTILING DP로 풀었다. 먼저 가능한 모든 경우의 수를 구해서 dp 배열에 저장한다. dp[i] = 사각형의 너비가 i일 때 가능한 타일링 방법의 수 = dp[n - 1] + dp[n - 2] 점화식은 위와 같다. dp[n-1]은 현재 칸에 1 * 2를 채울 때 가능한 타일링 방법의 수이고 dp[n-2]는 현재 칸과 다음 칸에 2 * 1 타일들로 채울 때 가능한 타일링 방법의 수이다. 모두 가능한 경우를 구했으면 대칭한 타일링 방법의 수를 구한다. 대칭한 경우는 위와 같다. 빨간색 부분과 파란색 부분이 같으면 대칭한 경우이다. 위 2개는 짝수인 경우이다. 짝수인 경우 반으로 나눈 부분(N/2)이 같은게 나올 때와 .. 2019. 6. 12. [algospot][PI] 원주율 외우기 문제 : https://algospot.com/judge/problem/read/PI DP 문제로 풀었다. dp[ind] = 문자열[ind~끝]으로 구할 수 있는 최소 난이도. = 최소값(문자열[ind~ind+len)의 난이도 + dp[ind+len]) (3 2019. 6. 8. 이전 1 ··· 5 6 7 8 9 다음
