김머성 블로그

[BAE/<JOON> 문제풀이] 3943. 헤일스톤 수열 (DP.040)

https://www.acmicpc.net/problem/3943 3943번: 헤일스톤 수열 문제 헤일스톤 수열은 다음과 같이 정의 한다. n이 짝수라면, 2로 나눈다. n이 홀수라면, 3을 곱한 뒤 1을 더한다. 헤일스톤 추측은 임의의 양의 정수 n으로 수열을 시작한다면, 항상 4, 2, 1, 4, 2, 1,.. www.acmicpc.net 파일 합치기 풀다가 시간 딸림. 근데 이 문제도 오래걸림 앞으로 iostream 걸러야겠다. 무조건 cstdio쓴다. cin.tie(NULL), ios_base::sync어쩌구 쓰고 푸는데 안되서 혹시나하고 scanf printf쓰니까 바로 맞는다 더보기 #define _CRT_SECURE_NO_WARNINGS #include #include using namesp..

[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