c언어 27210번 신을 모시는 사당 (백준)

#include <stdio.h>

int main(void)
{
	int n;
	scanf("%d", &n);
	
	int one = 0, two = 0, max = 0, tmp;
	while(n--) {
		scanf("%d", &tmp);
		if(tmp == 1) {
			one++;
			two--;
			if(one < 1) one = 1;
			if(one > max) max = one;
		} else {
			two++;
			one--;
			if(two < 1) two = 1;
			if(two > max) max = two;
		}
	} printf("%d", max);
}

풀이 : dynamic programming

 

왼쪽은 1, 오른쪽은 2로 볼 때

 

one은 (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수)이며

two은 (오른쪽을 바라보는 금색 돌상의 개수) - (왼쪽을 바라보는 금색 돌상의 개수)입니다.

 

1이면 one++, two--

2이면 one--, two++

을 합니다.

 

만약 1이 입력되었을 때 이전까지의 one의 값이 1 미만이면 1을 대입합니다.

만약 2가 입력되었을 때 이전까지의 two의 값이 1 미만이면 1을 대입합니다.

 

또한  one  또는 two의 값이 max보다 크다면 max에 대입해 줍니다.

 

마지막으로 max을 출력합니다.