못 풀면 풀이를 보고 습득하는 능력을 키워보자.....
1915번 가장 큰 정사각형
1. 왜 dp[i][j]를 i,j를 포함하는 가장 큰 정사각형의 길이로 잡았을까?
방법과 구하는것(정사각형의 넓이) 사이에 연결 고리가 있을 텐데.
정사각형을 구하려고 생각해 보면 매우 추상적이다. -> 이것을 i,j를 끝으로 하는 정사각형으로 잡아 주므로서 해결된다?
2. 작은 정사각형들로 부터 큰 정사각형이 만들어지는지?
즉 아래 dp로 부터 dp[i][j]를 어떻게 형성하는지 제대로 몰랐다.
틀린 이유
배열 사이즈를 NM으로 안하고 NN으로 했다.
그리고 dp가 dp[i-1] 같이 계산되는 부분이 있는데 인덱스가 0부터 시작해서 끝까지 확인하지 못한거 같다.
고칠점 - 명시적;
i-1이 들어가면 그냥 배열을 1부터 받자......
고칠점 - 추상적;;;
dp[i][j]를 정하지 못한 부분 , 부분 문제를 정의하지 못했어, 구하려는 dp[i][j]를 어떻게 다른 dp를 이용해서 구할지 방법을 찾지 못했다.
11049번 행렬의 곱셈 순서
dp[i][j] i~j까지 연산 횟수의 최대값.
dp[i][j] = max(dp[i+1][j] + arr[i]*arr[i+1] , dp[i][j-1] + arr[j-1]*arr[j]);
사실 이 생각은 했다. 아 조금 다르다. 내 생각은 위처럼 하나씩 확장해 나갈 생각이였다.
DP[i][j]=min(DP[i][j],DP[i][k]+DP[k+1][j]+di−1∗dk∗dj) 이걸로 해야 계산이 편한듯?
그리고 행렬 연산 결과 r,c를 저장해야 한다 생각했는데 그게 아니라 행렬의 맨 앞뒤 수로 사용 한다.
그런데 구현을 어떻게 할지가 문제 였다. 그리고 이게 과연 맞을까 확신도 안들었따.
반복문으로 구현하면 어디서 부터 어디까지로 구해줘야 되는지 모르겠다.
답안 코드를 보니 재귀로 구현했다. 보고 나니까 병합 정렬이랑 매커니즘이 비슷하다..... 이걸 눈치 못챈게 일단 문제라 본다.
1. 아무리 봐도 다른 사람들 아이디어는 보기만 해도 정확한거 같고, 구현도 깔금해진다.
일단 내 아이디어는 맞는가 생각해보자. 음.... 잘 모르겠다. 왜 모르는걸까 여기서 내가 이것만 확실히 해도 좋을텐데.....
ab((cdt)e)f
ab(cd)(te)f
7579번 앱 문제
아이디어는 나도 생각했었다. 그런데 dp 구성을 어떻게해야 될지 감이 안잡ㅇ혔다.
그런데 풀이를 보아도 구현 방식이 각자다 다른데 어떻게 이해해야 할지 모르겠다;;
dp[i][j] : i번째 앱까지중 j 코스트로 얻을 수 있는 최대 바이트수인데 i번째 앱까지를 스테이트에 넣을 생각을 못했다.
왜 넣은거지???????
약간 그런쪽으로 생각하긴했었는데 지금 말하는 방식의 구현은 해답을 봐도 어렵다. 선택하는 조합으로 보아서 2^100가지중에 메모이제이션으로 줄여줄려고 했다.
다른 방법은 이중 반복문으로 탑 다운 방식이 되던데 그게 왜 되는지 모르겠다. 구하지도 않은 큰 값으로 부터 작은 값을 구한다는게 말이 되나? 나는 그래서 약간 구한 값부터 시작하려고 애를 썼는데 그렇게 한건 못찾았다.....!@#!@#?!@??
이런 식의 구현이 왜 가능하지 ? <https://huiung.tistory.com/120>
#include <iostream>
using namespace std;
#define INF 987654321
int byte[101];
int cost[101];
int dp[101][10001];
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int N,M; cin >> N >> M;
for(int i = 0; i < N; i++)
cin >> byte[i];
for(int i = 0; i < N; i++)
cin >> cost[i];
int ans = INF;
dp[0][cost[0]] = byte[0];
for(int i = 1; i < N; i++) {
for(int j = 0; j <= 10000; j++) {
if(j-cost[i] >= 0)
dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]]+byte[i]);
dp[i][j] = max(dp[i][j], dp[i-1][j]);
if(dp[i][j] >= M) {
ans = min(ans, j);
}
}
}
cout<<ans;
return 0;
}약간 느낌이 벨만 포드같은데 간선의 갯수 만큼 업데이트 해주는거 같다 벨만 포드!
11062번 : 카드 게임
아이디어는 좀 생각한거 같다. 모든 각 지점에서 확장하며 카드를 골라보려고 했다.
답안을 보니 위를 구현하기 보다. 전체 범위에서 좁혀오는 식으로 구현했따.
뭔가 자꾸 큰 문제를 풀려고는 하는데 작은 문제 부터 풀려야 그게 될거같은 느낌이였다. 근데 잘 생각해보면 재귀로 구현해 놓으면 작은것을 알아서 풀어서 오는 백트래킹 방식이 아닌가....
3차원 디피 일때 min으로 저장하는게 의미가 있는건가???????
min max tree라 한다. (https://m.blog.naver.com/PostView.nhn?blogId=zzabbo&logNo=70076811364&proxyReferer=https%3A%2F%2Fwww.google.com%2F)
이해는 잘 안된다.
일단 st,dt에 따른 스테이트는 근우 또는 명우 둘중 단 한개이다.
아 근데 근우 입장에서 명우가 최소가 되게 선택해야 게임이 말이 되니까 그말이 무슨말인지 좀 이해될거 같다....!!
근데 왜틀리지 ㅠ
배열 범위가 500으로 작았었따;
이건 탑 다운 방식으로 구현해야 구현이 쉽다; 바텀업도 가능한가? -> 일단 제쳐두자;; 그렇게 푸는건 아직 잘 모르겠다;;