The Way
5월 12일 백준 본문
* 코드는 맨 아래에 있습니다
하루에 7시간씩 문제풀기 이틀째이다. 실력이 늘..고있다고 믿는다.
오늘은 DP 문제들 위주로 풀었다.
# 백준 1520번: 내리막 길
기본적인 DP 문제
* 메모리 초기화 시키기
#include <memory.h> int arr[num1][num2]; memset(arr, -1, sizeof(arr));
# 백준 1912번: 연속합
유명한 DP문제인 연속합이다.
한가지 유의할 점은 숫자는 한 개 이상 선택해야 한다는 것. 즉 모두 다 음수이면 제일 큰 값을 골라주어야 한다.
# 백준 10844번: 쉬운 계단 수
맨 뒷자리수별로 구분해주어야한다. 0과 9는 1 차이가 아니라 9 차이이기 때문..
# 백준 11053번: 가장 긴 증가하는 부분 수열
이것 역시 고전적인 문제. 일단 $O(n^2)$으로 코딩해보았다.
# 백준 12015번: 가장 긴 증가하는 부분 수열 2
# 백준 12738번: 가장 긴 증가하는 부분 수열 3
n이 커져서 $O(n^2)$ 알고리즘으로는 풀 수가 없다.
다행히도, $O(n\log{n})$짜리 알고리즘이 존재한다.
문제가 완전히 동일하다. 공짜로 한 문제를 준 것에 감사를 표한다♡
최대 부분 수열 길이를 실수로 10010으로 했는데, 오류가 나지 않은 걸 보니 그렇게 길지는 않은가보다.
# 백준 14002번: 가장 긴 증가하는 부분 수열 4
# 백준 14003번: 가장 긴 증가하는 부분 수열 5
위의 것에 수열의 출력까지 추가로 해야한다.
알고리즘이 상당히 복잡해지는데, 원소를 갱신할 때마다 그 정보를 기록해줘야한다. 시간이 상당히 오래 걸린다.
시간 줄여본다고 열심히 해봤는데 더 늘더라.. 아직 vector의 copy 등에 그렇게 익숙하지는 않은 것 같다. 더 공부해야겠다.
다 풀고보니 끝내주는 알고리즘을 찾았다. 그냥 몇 번째로 들어가는지 보고, 끝에서부터 다시 훑어주면 되더라. 그걸 바탕으로 코드를 재작성해보았다.
14002번이 원래 내가 작성한 것, 14003번 새로 작성한 코드이다.
# 백준 11727번: 2×n 타일링 2
기본적인 DP 문제
# 백준 2293번: 동전 1
메모리를 4MB밖에 안줘서 나름 까다로운 DP 문제라고 생각했다.
내가 푼 방식은 동전 각각의 금액을 나열했을 때, i번째 인덱스까지 사용해서 만들 수 있는 갯수를 구하고 i+1번째를 점화식으로 구하였다. 메모리가 없어서 아래서부터 모든 경우를 계산해가며 올라갔다.
풀고 맞은 사람 코드를 보니 생각보다 너무 간단하게도 풀린다.
동전이 중복이 없다는 조건이 없어서 set으로 중복체크를 했는데, 다른 사람 푼 걸 보니 중복이 없는 것 같다..
# 백준 9465번: 스티커
기본적인 DP 문제
# 백준 9461번: 파도반 수열
"훗 내가 long long 범위에 속을 듯 싶더냐"
n = 60쯤 되면 int 범위를 넘으므로 long long을 사용해야 한다
# 백준 2167번: 2차원 배열의 합
굉장히 유명한 문제 중 하나인 2차원 배열의 합 구하기
(0, 0) ~ (i, j) 사이의 합을 저장하고 있으면 임의의 구간
(a, b) ~ (c, d) 사이의 합을 O(1)에 구할 수 있다.
식은 (c, d) - (a - 1, d) - (c, b - 1) + (a - 1, b - 1)이다
# 백준 11057번: 오르막 수
기본적인 DP 문제.
수를 n으로 나눈 나머지를 구할 때는, 혹시 뒤에서 sum을 해줄 일이 있으면 sum 한 다음에도 나머지 연산을 해야 한다는 것 잊지 말자..
# 백준 2294번: 동전 2
기본적인 DP 문제. 동전 1보다 체감상 더 쉬운 것 같기도 하다.
존재하지 않을 조건을 잘 따지고, 어떻게 저장할지 잘 생각하자.
# 백준 11048번: 이동하기
생략
# 백준 2133번: 타일 채우기
점화식 관계를 찾는 것이 참 오래 걸렸다 ㅠㅠ
내가 찾은 관계는 다음과 같다. 먼저 n이 홀수일 때는 답이 0이다.
n이 짝수일 때는 '나눌 수 없는' 길이 n의 갯수를 먼저 파악하자.
n = 2일 때는 3, 나머지는 2이다.
이제 점화식 관계를 찾자. 설명하기 어려우므로 예시를 들자.
길이 8일 때 맨 오른쪽 '나눌 수 없는 것'의 길이를 생각하자. 아래 4가지 경우가 있다.
(모든 6) + (나눌 수 없는 2) -> P(6) * 3
(모든 4) + (나눌 수 없는 4) -> P(4) * 2
(모든 2) + (나눌 수 없는 6) -> P(2) * 2
나눌 수 없는 8 -> 2
따라서 P(8) = 3 * P(6) + 2 * P(4) + 2 * P(2) + 2
이런 식의 점화식이 나온다.
# 백준 11055번: 가장 큰 증가 부분 수열
11053번의 단순한 변형.
# 백준 9251번: LCS
최장 공통부분 수열 문제. 이 또한 고전적인 유명한 문제이다.
# 백준 1373번: 2진수 8진수
오늘 할당량을 다 풀고 보니 랭킹이 1003등이라서 뭔가 랭킹 1000등을 뚫고 싶어졌다. 그래서 제일 쉬워보이는 문제로 골랐다. 딱히 설명할 것은 없다.
이 문제를 푸니 랭킹 999등이 됐다. 기부니가 좋구나~ 허허허~
1373.cpp