BOJ 2342 - dance dance revolution 문제 링크https://www.acmicpc.net/problem/2342 문제 해결 1. dp[l][r][stage] : 현재 stage에서 왼발이 l, 오른발이 r에 위치할 때 사용한 최소의 힘 주의할 점 || 생각해볼 점 1. 그리디라고 생각할 수 있지만 항상 현재 해가 최적이 될 수 없다. 아래는 현재 상황에서 가장 적은 힘을 사용해서 움직였을 때의 cost. 아래는 현재 상황에서 가장 적은 힘을 사용해서 움직였을 때의 cost. 그리디로 해결할 수 없다. 그러므로 DP를 이용해서 해결해야한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 6086 - 최대 유량 문제 링크https://www.acmicpc.net/problem/6086 문제 해결 1. 기본적인 Maximum Flow 문제다. 주의할 점 || 생각해볼 점 1. 시간 복잡도 O(VE^2)을 위해서 BFS를 이용한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 5675 - 음주 코딩 문제 링크https://www.acmicpc.net/problem/5676 문제 해결 1. 수열의 크기, 쿼리 모두 최대 이므로, segment tree를 이용한다. 2. segment tree를 initialize할 때, 양수면 1, 음수면 -1, 0이면 0을 tree[node]에 넣어준다. 주의할 점 || 생각해볼 점 1. 값을 구하는 쿼리에서 범위를 넘어가게되면 1을 출력한다. 왜냐면 1은 양, 음, 0 에 영향을 끼치지 않기 때문이다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 ··· 14 15 16 17 18 19 20 ··· 32 다음
