(백준 2193번/1904번 이친수/01타일 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법

DP만 잘 알아도 코테가 쉬워진다는 말을 어디서 들은 적이 있는뎁...!ㅎㅎ 라이님 블로그를 보면서 실력을 키워보쟈!

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220777103650&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

동적 계획법(Dynamic Programming) (수정: 2019-02-07)

 

🚨위 블로그에 있는 문제(1463번 1로 만들기, 9465번 스티커, 2294번 스티커)는 내 Tistory에서 따로 코드를 올리지 않을 예정이다. 또한 나의 모든 DP 풀이는 위 블로그에 있는 코드를 정답 코드로 생각하고 응용해서 푼 코드다!!

 

DP는 재귀함수를 사용하는 탑다운 방식과 반복문을 사용하는 바텀업 방식이 존재한다. 나도 개인적으로 직관적인 탑다운 방식을 선호하기는 하는데, 풀리기만 한다면 어떤 방식이든 다 좋다..😊

 

라이님 블로그에서 풀어준 문제는 다음과 같다.

   1. 피보나치 수열 문제

   2. 백준 1463번 : 1로 만들기   ← 점화식을 만드는 방식을 눈여겨보자

★3. 백준 9465번 : 스티커         ← 점화식의 변수를 2개로 만드는 방식을 눈여겨보자

★4. 백준 2294번 : 동전 2          ← Base case를 설정하는 방식을 눈여겨보자

 

dp 문제를 풀 때 지켜야 할 것

1. dp배열의 크기를 잘 정해야한다.

(스티커의 경우 2 * n 배열을 입력으로 받으며, dp 배열은 n * 3의 크기로 지정했다.)

2. dp배열은 문제를 풀면서 절대로 나올 수 없는 수로 초기화한다.

(피보나치수와 같이 양의 정수만이 답이 될 경우 -1로 초기화한다)

3. Base case를 꼼꼼하게 설정한다.

4. int result = ~로 정하고, max/min함수를 이용해서 업데이트하면 된다. 

5. 탑다운 방식은 처음부터 정답을 호출하고, 바텀업 방식은 Base 케이스부터 올라간다.

 

(참고)

$(A+B) % M = (A%M + B%M) %M$

$(A-B) % M = (A%M - B%M) %M$

$(A*B) % M = (A%M * B%M) %M$

 

정수 리스트 초기화 하기

dp를 하기 위해서는 배열을 원하는 숫자로 초기화할 줄 알아야 한다!

int dp[100] = {5} 의 결과가 {5, 0, 0, ...., 0}이기 때문에 다른 방법으로 초기화해야 하는데, 많이 쓰는 방법은 memset과 fill이 있다. 

1. fill 사용법(fill_n)

https://zynar.tistory.com/90

(매우 자세히 잘 알려준다!!)

[C++] fill, fill_n 배열을 초기화 하는 방법, 2차원, 3차원 배열 초기화

//fill(시작 주소, 끝 주소, 변경 값);

int iarr[9];
fill(iarr, iarr + 9, 5);
fill(iarr, iarr +sizeof(iarr) / sizepf(iarr[0]), 5};
fill(&iarr[0], &iarr[9], 5);
fill(&iarr[0], &iarr[sizeof iarr / sizeof iarr[0]], 5);

//fill_n(시작 주소, 몇 번 할지, 변경 값);

int iarr[9];
fill_n(iarr, 9, 5);
fill_n(iarr,sizeof(iarr) / sizepf(iarr[0]), 5};
fill_n(&iarr[0], 9, 5);
fill_n(&iarr[0], sizeof iarr / sizeof iarr[0], 5);

 

2. memset 사용법

https://blockdmask.tistory.com/441

[C언어/C++] memset 함수 메모리 초기화

//memset(변경하고자 하는 목적지의 첫번째 주소, 변경하고자 하는 값, 변경하고자 하는 길이 * sizeof(type))

char arr1[] = "HelloWorld";
memset(arr1, 'c', 5 * sizeof(char)); 
//  출력 결과 : cccccWorld

* 0과 char 타입 초기화에만 사용 가능하다!

백준 2193번

https://www.acmicpc.net/problem/2193

2193번: 이친수

 

규칙성을 찾다가 보니 피보나치 수열과 같이 풀면 되는 문제였다!

종이가 없어서 급하게 냅킨에,,

 

쉽다고 생각했는데...

???????

틀렸다고 해서 당황했다. 롱롱 문제가 아닐까 했는데 역시나 long long문제였다.

피보나치수도 잘 보면 숫자가 급격하게 커지는데, 이 문제도 피보나치 90번째 수를 부르는 것과 동일한 문제라서 터진 것 같았다.

 

맞는거 같은데 틀리는 분들은 int를 long long으로 바꿔보세용!!!

//백준 2193번

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>

const long long MAX = 90 + 1;
long long dp[MAX];

long long f(long long N) {
	// N == 1 : 1
	if (N == 1) return 1;
	//  N == 2 : 10
	if (N == 2) return 1;
	// N == 3 : 100, 101
	if (N == 3) return 2;
	if (dp[N] != -1) return dp[N];

	dp[N] = f(N - 1) + f(N-2);
	return dp[N];
}

int main() {
	long long N; scanf("%lld", &N);
	std::fill_n(dp, MAX, -1);
	printf("%lld", f(N));
	return 0;
}

 

 

백준 1904번

https://www.acmicpc.net/problem/1904

1904번: 01타일

 

백준 1904번은 2193번 이친수 문제에서 초기값만 바꿔주면 바로 풀 수 있다.

//백준 1904번

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>

const long long MAX = 1000000 + 1;
long long dp[MAX];

long long f(long long N) {
	// N == 1 : 1
	if (N == 1) return 1;
	//  N == 2 : 10
	if (N == 2) return 2;
	// N == 3 : 100, 101
	if (N == 3) return 3;
	if (dp[N] != -1) return dp[N];

	dp[N] = (f(N - 1)%15746 + f(N-2) % 15746) % 15746;
	return dp[N];
}

int main() {
	long long N; scanf("%lld", &N);
	std::fill_n(dp, MAX, -1);
	printf("%lld", f(N));
	return 0;
}

 

과거 풀이를 보니 바텀업 방식으로 풀었던데, 바텀업 방식이 확실히 메모리와 시간이 적게 걸리는 것 같다.

 

아래는 과거의 바텀업 풀이!!

#백준 1904번
#include <cstdio>

int Arr[1000023];

int main(void){
	int n,i;
	i = 4;
	scanf("%d", &n);
	Arr[1] = 1;Arr[2] = 2;Arr[3] = 3;
	for(i=4;i<1000010;i++){
			Arr[i] = ((Arr[i-1]+Arr[i-2])%15746);
	}
	printf("%d", Arr[n]%15746);
	return 0;
}