9780. 외계인 침공

 

이 문제는 전형적인 DP 문제입니다. 

하지만, DP에 약한 저는 타블로그를 참고하여 포인트를 얻었습니다. ㅠㅜ

 

Solution 

문제를 읽어보면, 2가지의 규칙을 찾을 수 있습니다.

1. 침공당한 도시의 인접한 도시는 침공할 수 없다. -> 침략을 하면 무조건 한칸은 뛰어야한다.
2. 도시는 침공 당한 도시와 당하지 않는 도시로 나뉘어진다.

이 두가지 규칙을 가지고 DB식을 세울 수 있습니다. 

DB[i] = max(DB[i-1],DB[i-2]+problem[i]);

DB[i]는 i-1번째 도시까지의 max값(DB[i-1])이랑 i-2번째 도시를 방문하고 i번째의 도시를 방문하는 값(DB[i-1]+problem[i])을 비교하여 더 큰값을 가지면 됩니다.  

Key Point

1. 왜인지 모르겠지만, 타임오버가 났다. 이를 해결하기위해서 cin/cout을 printf/scanf로 바꾸었습니다.
2. 총 2가지의 솔류션을 생각했습니다. 10^6까지의 배열을 만들기에는 공간이 낭비된다고 생각하여 필요한 값 3가지(2번째 전 값, 1번째 전 값, 현재 값)를 가지는 배열을 선언하였습니다.
3. 또한, 입력은 받는 즉시 계산을 하기 때문에 데이터량만큼 도는 for이 한개만 존재하게 됩니다. 

 

#include <stdio.h>
long long max(long long a,long long b) {
	return a > b ? a : b;
}
long long list[1000010];
int main(void) {

	long long tc = 0;
	scanf("%lld", &tc);
	long long box;
    long long number = 0;
	for (int i = 0; i < tc; i++) {
		scanf("%lld", &number);
		scanf("%lld",&list[1]);
        list[0]=0;
		for (int j = 1; j < number; j++) {
			scanf("%lld",&list[j+1]);
			list[j+1]= max(list[j+1] + list[j-1], list[j]);
		}
		printf( "#%d %lld\n", i+1,list[number]);

	}
	return 0;
}

 

#include <stdio.h>
#include <iostream>
using namespace std;
long long max(int a,int b) {
	return a > b ? a : b;
}
int main(void) {

	long long tc = 0;
	scanf("%lld", &tc);
	for (int i = 0; i < tc; i++) {
		long long  number = 0;
		scanf("%lld", &number);
		long long list[3] = { 0 };
		long long box;
		scanf("%lld", &list[1]);
		for (int j = 1; j < number; j++) {
			scanf("%lld", &list[2]);
			box = max(list[0] + list[2], list[1]);
			list[0] = list[1];
			list[1] = box;
			list[2] = 0;
		}
		printf("#%d %lld\n", i + 1, max(list[0], list[1]));
	}
	return 0;
}

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXE0gpIa3dADFAVX&categoryId=AXE0gpIa3dADFAVX&categoryType=CODE

SW Expert Academy