[BOJ] 2579 계단오르기, C Macro function(매크로함수)

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

2579번: 계단 오르기

 

실수를 남기는 글입니다.

 

풀이방법 : DP

 

DP는 어떻게 풀까요..

이론상 O(N)인데, 이 안에 맞추려면

점화식을 찾고, 이전에 계산한 내용으로 다음 내용을 맞추죠.

테이블을 채워나간다고 생각하더라구요.

뭐 지금 그렇게 느끼고 있습니다.

 

이건 2차원 배열로 풀었습니다. DP table을 왜 2차원으로 만드는 생각은 못했을까요.

항상 다른 방향으로 생각하자고 생각하는데.. 열정으로 노력합시다!! 열정!!

 

규칙 :

1칸을 올라갔으면, 다음번엔 또 1칸을 갈 수 없습니다.

1칸 -> 1칸 (불가)

1칸 -> 2칸 -> 1칸 (가능)

1칸 -> 2칸 -> 2칸 ->2칸 -> 1칸 (가능)

2칸 -> 2칸 -> 2칸 (가능)

ㅇㅋ 이런느낌입니다.

 

초기값 :

dp[n][0] : 2칸 이동했을때 최대로 나올 수 있는 수

dp[n][1] : 1칸 이동했을때 최대로 나올 수 있는 숫자.

 

쓰는건 저렇게 썼지만,

dp[n][0]은 불법(1칸->1칸)을 제외한 어떠한 방법이라도 써서 n번째 칸에 도착했을때 점수의 최대 합으로 생각했습니다. (바로 전에는 2칸 뛴거)

dp[n][1] 은 불법을 제외한 어떤 방법이라도 써서 n번째 칸에 도착했을때 점수의 최대 합으로 생각했습니다. (바로 전에는 1칸뛴거)

 

그래서 max(dp[n][0], dp[n][1]) 으로 하면, 어떻게 불법을 저지르지 않고 잘 계단을 뛰어서 최대 점수를 뽑아낸거라고 생각했습니다.

 

dp[305][2]; 로 배열을 잡았습니다.

dp[n][0] => 2칸씩 간 경우

dp[n][1] => 1칸씩 간 경우

이렇게 생각을 했습니다. dp[n][1], dp[n][2] 이렇게 직관적으로 해도 됩니다. 모든건 자기의 맘대로..

dp[1]과 dp[2]는 경우의수가 정해져있어서 직접 그냥 초기값으로 찍어줬습니다.

규칙대로라면, 1칸을 이동했으면 dp[n+1][1]로 가야합니다. 그리고 dp[x][1] 에 있는 원소들은 무조건 dp[x+2][0]으로 가야합니다.

왜일까요? 1칸 1칸 이렇게 가면 안됩니다. 따라서 2칸이동을 해야하고, 2칸을 이동한 경우에는 1칸, 2칸 모두 가능하기에 [0]으로 보내는겁니다.

 

즉, dp[n][0]에서는 dp[n+1][1], dp[n+2][2] 둘다 가능하지만, dp[n][1]에서는 dp[n+2][0] 만 가능합니다.

*dp[1][1]이 아닌 dp[1][0]에 stair[1] 이 있는 이유는, 시작점은 계단으로 포함하지 않기 때문입니다.

 

초기값을 주면 규칙이 나옵니다.

원소 3을 예시로 들어보면,

dp[3][0] = stair[3] + max( dp[1][0], dp[1][1]);

dp[3][1] = stair[3] + dp[2][0];

 

일반화하면

dp[n][0] = stair[n] + max( dp[n-2][0], dp[n-2][1]);

dp[n][1] = stair[n] + dp[n-1][0];

 

#include<cstdio>
#define max(a,b) ((a>b)?(a):(b))
int dp[305][2];
int stair[305];
int main(void)
{
	int sz;
	int res;
	scanf("%d",&sz);
	for(int i = 1; i <= sz; i++){
		scanf("%d",&stair[i]);
		if(i == 1){
			dp[i][0] = stair[i];
		}else if(i == 2){
			dp[i][0] = stair[i];
			dp[i][1] = stair[i]+stair[i-1];
		}
	}
	
	
	for(int i = 3; i <= sz; i++)
	{
		dp[i][0] = stair[i] + max(dp[i-2][0],dp[i-2][1]);
		dp[i][1] = stair[i] + dp[i-1][0];
	}
	
	printf("%d\n",max(dp[sz][0],dp[sz][1]));
	
	
	
	return 0;
}

 

#define max(a,b) (a) >= (b) ? (a) : (b);

때문에 1시간을 날렸습니다. 처음에 짠게 틀린줄알고 굉장히 고민했습니다.

max(a,b)를 하면 답이 나오는데, int a = 3 + max(3,5); 를 하니 3이 나온겁니다.

 

하지만 매크로가 어떻게 변환되는지 아니까 왜 틀린지 알았습니다.

그냥 그대로 컴파일전에 치환이 되는데, 이 과정에서 오류가 생겼습니다.

 

int a = 3 + (3) > (5) ? (3) : (5) ;

이렇게 바뀌는데 우선순위 문제때문에, 6 > 5 ? 3 : 5 로 바뀌어버립니다.

이건 그래서 이건 참이라서 3이 나온겁니다.

 

그래서 혹시나 해서

int a = -1 + (3) > (5) ? (3) : (5) 를 해보니 5가 나왔습니다.

 

그럼 어떻게 해결해야할까요?

 

#define max(a,b) ( (a) >= (b) ? (a) : (b) )

로 하면 됩니다. 맨날 이거 헷갈렸는데 이해를 하니까 이제 틀릴일이 없겠네요.

 

int a = -1 + ( (3) >= (5) ? (3): (5));

괄호가 먼저 계산되니 -1 + 5가 되어 4가 나오게 될 것입니다.

 

여기까지..

그럼 이만..