김머성 블로그

[BAE/<JOON> 문제풀이] 1915. 가장 큰 정사각형 (DP.039)

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 이게 왜 동적계획법 문제인지 모르겠다. 각각 위치에 무슨 정보를 써야 풀 수 있을까 고민하다가 그냥 브루트포스로 풀기로 했다. 각 지점을 왼쪽 위 꼭짓점으로 하는 정사각형의 존재여부를 검사한다. 주어지는 맵의 양변의 최대크기가 1000이므로 검사해야할 지점은 총 $10^6$개 각각의 검사 경우 갯수는 각각의 단계에 대해 $\sum\limits_{k=1}^{1000000}a_{k}$ 이므로 $a_{k}$ 를 적당한 시간에 연산 할 수 있다면 이 방법으로 충분히 풀 수 ..

[BAE/<JOON> 문제풀이] 1965. 상자넣기 (DP.038)

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 �� www.acmicpc.net 더보기 #include #include using namespace std; int main() { vector arr, dp; int n; cin >> n; arr.resize(n + 1); dp.resize(n + 1); for (int i = 1; i > arr[i]; } dp[1] = 1; for (int i = 2; i

[BAE/<JOON> 문제풀이] 6359. 만취한 상범 (DP.037)

https://www.acmicpc.net/problem/6359 6359번: 만취한 상범 문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정� www.acmicpc.net 더보기 #include using namespace std; int main() { int t; cin >> t; for (int k = 1; k > n; int i; for (i = 1; i * i

[BAE/<JOON> 문제풀이] 1937. 욕심쟁이 판다 (DP.036)

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 www.acmicpc.net 내리막길과 거의 같은 문제라서 수월하게 풀 수 있었던 것 같다. 문제의 요점은 깊이우선 탐색으로 발생하는 중복 탐색을 어떻게 효율적으..

[BAE/<JOON> 문제풀이] 1309. 동물원 (DP.035)

https://www.acmicpc.net/submit/1309 로그인 www.acmicpc.net 더보기 #include #include using namespace std; int main() { vector dp; int n; cin >> n; dp.resize(n + 1); int s = 3; dp[0] = 1; dp[1] = 2; for (int i = 2; i

[BAE/<JOON> 문제풀이] 2225. 합분해 (DP.034)

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 난이도 정말 잘 나뉘여져 있는 것 같다. 골드 5까지만 정확하게 할만하고 그 이상은 무조건 이틀 이상 걸린다. k값을 점화식에 어떻게 넣느냐가 헷갈리는 문제였다. 2가지 사항을 고려하며 풀 수 있다. 1. 0을 만들 수 있는 가짓수 2. [만들 숫자]와, [그 숫자를 만들기 위해 사용할 숫자의 갯수] 두가지이다. 이 두가지를 고려하며 아래항부터 계산하여 답을 구할 수 있다. 첫째, 숫자를 몇개를 사용하든 0을 만드는 경우의 수는 무조건 1가지이다. 덧셈의 순서를 고려하지 않더라도 0을 만들려면 0면 써야하기 때문이다...