노는 게 제일 좋아

증가수열과 비슷하다. 여기서 전깃줄이 겹칠 때 어떨 때 겹칠까 생각해보면 된다. https://www.acmicpc.net/problem/2565 #맞은 풀이 #include #include #include using namespace std; //A가 내가 고르는 것 B가 결과라고 해보자 //내가 고른 것이 이전에 고른 것의 결과보다 작아선 안된다. //다음 것은 내가 고른 것의 결과보다 항상 커야한다. //1번줄을 연결해서 2번줄의 결과를 얻었다면 //2번줄을 연결했을 때 2번보다 작은 결과를 얻어서는 안된다. //내가 순서대로 고르고 결과만 위의 조건에 맞게 하면 되겠다. //-> 전깃줄 순서대로 정렬 //전깃줄을 삭제하는 방법이 아닌 최대의 전깃줄 연결 방법 //-> 최대 5개의 전깃줄을 연결할 ..

증가수열을 어떻게 구하는지 알면 바로 푼다. https://www.acmicpc.net/problem/11054 #맞은 풀이 #include #include using namespace std; const int MAX = 1001; int N; int arr[MAX]; int dp[2][MAX];//0번째 정방향, 1번째 역방향 증가수열. int main(){ cin >> N; fill(dp[0], dp[0]+MAX, 1); //최소한 자기 자신을 포함하는 1의 길이를 가짐 fill(dp[1], dp[1]+MAX, 1); //최소한 자기 자신을 포함하는 1의 길이를 가짐 for(int i = 1; i> arr[i]; } //dp[0][N]은 N번째 원소를 마지막으로 하는 증가 수열의 길이를 말함 for..

이것 내가 현재 칸에 있다면 어떤 칸을 거쳐서 오는 것이 좋은가? 어느 칸에서 올 수 있는가? 현재 칸을 오면 사탕개수가 어떻게 되는가? 를 생각하자 https://www.acmicpc.net/problem/11048 #맞는 풀이 #include #include using namespace std; const int MAX = 1001; int N, M; int map[MAX][MAX]; int dp[MAX][MAX]; int main() { cin >> N >> M; for (int i = 1; i map[i][j]; } } //초기 값 1행과 1열 값 초기화 (0행, 0열의 성분은 0임) dp[1][1] = map[1][1]; //1행 for (int i = 2; i

항상 N번째 일때는 어떻게 해야 가장 길어질까? 이전의 어느 원소를 가져와야할까?? 생각을 해보자 https://www.acmicpc.net/problem/11053 #맞는 풀이 #include #include using namespace std; const int MAX = 1001; int N; int arr[MAX]; int dp[MAX]; int main(){ cin >> N; int ans = 0; for(int i = 1; i> x; arr[i] = x; } //초기값 fill(dp, dp+1001, 1); //자기자신은 항상 포함되므로 최소 1 for(int i = 1; i

이 문제도 DP다. 과연 N번째 동전은 어느 것을 가져와야할까?를 생각해보자 N-1번째 동전은 무엇을 쓰는 것이 좋을까 생각해보자 https://www.acmicpc.net/problem/2294 #맞는 풀이 #include #include #include using namespace std; const int MAX = 10001; int N,K; int dp[MAX]; vector vec; int main(){ cin >> N >> K; fill(dp, dp+10001, MAX); //우선 min에 걸리지 않게 충분히 크게 MAX로 초기화 for(int i = 0; i> x; vec.push_back(x); if(x>10000)continue; //어차피 K보다 가치가 큰 동전은 쓰지 않음 dp[x]..

DP 중에서 하다보면 규칙을 찾는 것이다. 규칙을 2분만에 찾아서 바로 풀 수 있었다. 하지만 잘 보이지 않는다면.. 조금 힘들다. 항상 N-1과 N의 관계를 생각하면 될 것 같다. https://www.acmicpc.net/problem/11057 #맞는 풀이 #include using namespace std; int dp[1001][10]; int N; int main(){ cin >> N; //초기값 for(int i = 0; i

감이 안잡히면 가장 어려운게 DP가 아닐까.. 이것도 그렇다. https://www.acmicpc.net/problem/1915 #맞는 풀이 #include #include #include #include using namespace std; int n, m; int map[1001][1001]; int main() { cin >> n >> m; //최솟값 int ans = 0; for (int i = 0; i > s; for (int j = 0; j < m; j++) { map[i][j] = s[j] - '0'; //만약 1이 등장하면 최소 ans = 1 if (map[i][j] == 1) ans = 1; } } //1,1부터 시작하므로 나머지에 대한 계..

플로이드 알고리즘 적용해서 풀었다. 크리스마스 쉬고와서 그런지.. 머리가 하나도 안돌아간다. https://www.acmicpc.net/problem/1389 #맞는 풀이 #include #include #include #include #define INF 123456789 using namespace std; int cost[105][105]; int N,M; int main(){ cin >> N >> M; for(int i = 1; i from >> to; cost[from][to] = 1; cost[to][from] = 1; } //자기 자신으로 돌아오는 경로도 있어서 초기화 시켜줘야함 최단 경로 0으로 for (int i = 1; i

그냥 문제 이해가 조금 어려웠다. https://www.acmicpc.net/problem/2841 #맞는 풀이 #include #include #include using namespace std; int N, P; stack vec[7]; int main(){ cin >> N >> P; int cnt = 0; for(int i = 0; i> x >> y; //먼저 누르려는 것보다 아래를 연주하려는지 확인 while(!vec[x].empty()){ //가장 위 플랫을 제거 if(vec[x].top()>y){ cnt++; vec[x].pop(); }else break; } //손을 다 뗀 후에 //이미 누른 상태면 그냥 패스 if(!vec[x].empty()){ if(vec[x].top() == y)con..

물론 처음부터 생각은 안나겠지만 가장 DP다운 문제가 아닌가 싶다. 항상 N번째 항을 어떻게 구해야할까 생각하면 DP의 답은 나오지만.. 항상 생각나는 것은 아니다. https://www.acmicpc.net/problem/11055 #맞는 풀이 #include #include using namespace std; int N; int arr[1001]; int dp[1001]; int main(){ cin >> N; int ans = 0; for(int i = 1; i> arr[i]; } //dp[i] -> arr[i]를 증가 부분 수열의 마지막이라 할 때의 부분 수열의 합. //즉, 현재 위치의 값을 더한 것이 dp[i]에 저장됨 //dp[i]채우기 for(int i = 1; i