김머성 블로그

[BAE/<JOON> 문제풀이] 2096. 내려가기 (DP.044)

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 티어가 골드 4라서 여러울거라 생각했는데 되게 간단했다. 문제의 핵심은 10만개의 입력이 주어지는데 반해 허용되는 메모리 한계가 4MB라는 점이다. 사실 이 부분도 unsigned short 로 변수를 선언하면 200,000 즉, 2MB로 떨어지므로 10만개 짜리 배열 2개를 써도 풀리지 않을까 생각했는데 그건 아니더라. (아마도 패딩때문에 그런 것 같다) 로직 자체는 간단하므로 배열만 빼면 쉽게 풀린다...

[BAE/<JOON> 문제풀이] 2011. 암호코드 (DP.043)

https://www.acmicpc.net/problem/2011 2011번: 암호코드 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이� www.acmicpc.net 맞는 코드 짜놓고 컨트롤 c가 안먹어서 이전 코드로 제출하고 틀린거보고 왜틀렸는지 1시간 고민했다. 이 문제 함정이 많다. 1. 0으로 시작하는 문자열이 입력되는 경우 2. 10, 20처리 (30이상 제거) 3. 0이 2번 이상 반복되는 경우 처리 처음 풀 때 저 3가지 경우중 2가지 이상을 먼저 떠올리고 코드를 짰다면 당신은 천재다. 특히 2번이 처리하기 까다로웠다. 여러 방법이 있겠지만 고민 끝..

[BAE/<JOON> 문제풀이] 9252. LCS2 (DP.042)

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 기존 LCS를 추적해서 문자열을 뽑아내는 부분이 추가된 문제다. 공통부분문자열 알고리즘은 그대로 적용하고 최댓값을 탐색하기 위해서 사용했던 테이블을 그대로 복기하며 문자열을 뽑아주면 된다. 우선 최댓값이 들어간 위치를 미리 저장해놓고, 그 위치부터 역순으로 배열을 탐색하며 이전 길이의 문자열에서의 갱신이 몇번째 문자에서 이루어졌는지 짚어가며 출력한다..

[BAE/<JOON>] 11066. 파일 합치기 (DP.041)

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 �� www.acmicpc.net 바텀업 방식의 재귀를 사용하는 문제들은 다 너무 어려운 것 같다. 사실 이렇게 푸는게 맞는지도 잘 모르겠다. 다른 사람들 채점표도 봤는데 자바 파이썬으로 짠 코드가 대부분 1초안에 끝나는데 나 혼자 c쓰고 1.7초 걸렸다. 맞긴 했는데 좀 찝찝하다.. 풀이과정은 좀 더 깔끔하게 풀이하고 써야겠다. 이건 그냥 완전탐색 날림 풀이라서.. 더보기 #include #include /* 1 +..

[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}$ 를 적당한 시간에 연산 할 수 있다면 이 방법으로 충분히 풀 수 ..