HyeLog

앞서 푼 다이나믹 프로그래밍(dp) 문제들과는 점화식의 로직이 살짝 달랐다. j를 1~(i-1) 로 증가시켜가면서 d[i]값을 갱신하는 것이 핵심이었다. #include #include #define MAX 1001 using namespace std; int N, A[MAX], d[MAX], answer; void dp() { int maxD = 0; for (int i = 1; i A[j]) d[i] = max(d[i], d[j] + A[i]); } maxD = max(maxD, d[i]); } answer = maxD; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i > A..

다이나믹 프로그래밍(dp) 문제였다. 점화식을 세울 때 규칙을 잘 생각해봐야했다. 삼각형에서 제일 왼쪽 수, 제일 오른쪽 수, 가운데에 있는 수들 이 각각 다른 점화식을 갖는다. 윗단에서 선택한 숫자의 위치가 밑단에서 선택할 수 있는 숫자의 위치에 영향을 주기 때문이다. (왼쪽, 오른쪽 대각선) #include #include #define MAX 501 using namespace std; int n, d[MAX][MAX], arr[MAX][MAX], answer; void dp() { d[1][1] = arr[1][1]; for (int i = 1; i

다이나믹 프로그래밍(dp) 문제였다. d[i]가 i번째잔까지 왔을때 포도주를 최대로 마신 양 이라고 할 때, d[1]은 당연히 첫번째 잔을 마시는 것이고, d[2]는 첫번째 잔과 두번째 잔을 모두 마시는 것이다. 이후에는, 3가지 경우가 존재한다. ① 현재 i번째 잔을 안마시는경우 ② 현재 i번째 잔을 마시는데, 그 전 i-1번째 잔은 안마신 경우 ③ 현재 i번째 잔을 마시는데, 그 전 i-1번째 잔도 마신 경우 -> 이 경우, i-2번째 잔은 안마셨어야 함. 이 3가지 경우 중 최댓값이 d[i]다. #include #include #define MAX 10001 using namespace std; int n, d[MAX], wine[MAX]; void dp() { d[1] = wine[1]; d[2]..

다이나믹 프로그래밍(dp) 문제였다. d[i][j]는 자릿수가 i일때 마지막이 j인 오르막수의 개수이다. 마지막이 j려면 그 전 숫자 (자릿수가 i-1인 숫자 = d[i-1][☆] ) 에서 ☆에 들어갈 숫자가 0, 1, 2, ··· j 여야 한다. (그래야 오르막수이다.) 따라서, 모든 경우를 3중 for문을 통해 계산할 수 있었다. 첫번째 for문은 자릿수를 증가시키고, 두번째 for문은 해당 자릿수인 숫자의 마지막 수가 무엇인지 따지고, 세번째 for문은 마지막 수를 고려해서, 그 전 숫자(자릿수가 하나 적은)의 값들을 더함으로써 실제로 오르막수의 개수를 구하기 위해 사용된다. #include #define MAX 1001 #define MOD 10007 using namespace std; int ..

다이나믹 프로그래밍(dp) 문제였다. 가로 i번째 줄에 대해서 사자를 1번째칸에 배치하는 경우 / 2번째칸에 배치하는 경우 / 배치하지 않는 경우 -> 총 3가지 경우에 대해 점화식을 세웠다. 이때 i-1번째 줄의 사자와 가로, 세로로 붙어있을 수 없다는 점을 이용해야 한다. #include #define MAX 100001 #define MOD 9901 using namespace std; int N, answer; long long d[MAX][3]; // 0: 세로 1번째칸 / 1: 세로 2번째칸 / 2: 배치 X void dp() { d[1][0] = 1; d[1][1] = 1; d[1][2] = 1; for (int i = 2; i > N; dp(); cout

다이나믹 프로그래밍(dp) 문제였다. 해당 집의 색깔이 R,G,B 일때 각각의 경우에 대해 해당 집까지 칠하는데 드는 총 비용을 total 배열에 저장해서 점화식을 세웠다. i번째 집이 R색깔이면, i-1번째 집은 G나 B색깔이다. #include #include // min() #define MAX 1001 using namespace std; int N, answer; int RGB[MAX][3]; int total[MAX][3]; // 해당 집의 색깔이 R,G,B 일때 각각 해당 집까지 칠하는데 드는 총 비용 void dp() { total[1][0] = RGB[1][0]; total[1][1] = RGB[1][1]; total[1][2] = RGB[1][2]; for (int i = 2; i > ..

☆ , 헤더 파일 include해야함 min_element(v.begin(), v.end()) 는 벡터의 최솟값을 가리키는 포인터를 리턴함. 따라서 이 포인터에서 v.begin()을 빼면, 최솟값이 몇번째 값인지 그 인덱스를 알 수 있음! int min_index = min_element(v.begin(), v.end()) - v.begin(); cout

재귀를 이용해서 풀었다. 재귀 함수로 정수 문자열을 만들고, 정수 문자열의 길이가 k+1 이 되면, 이 문자열이 부등호를 만족하는지 check 함수로 확인했다. 만족하면, 정답 후보에 저장했다. #include #include #include #include #define MAX 10 using namespace std; int k; vector v; bool visited[MAX]; vector ans; bool check(string num_str) { // 부등호 만족하는지 확인 for (int i = 0; i < k; i++) { if (v[i] == '') { if (num_str[i] < num_str[i + 1]) return false; } } return true; } void solve..