이것 저것 &

전형적인 dp문제입니다.

반복문으로 arr배열을 탐색하면서 

자신보다 arr값이 작고 dp값이 가장큰 값에 자신의 arr값을 더한값이 dp값이 되는 점화식입니다. 

즉 , dp[i] = arr[i] + dp[maxed_index]의 형태가 됩니다.

전체코드입니다:)

#include <iostream>
using namespace std;

int n, result = 0;
int arr[1001] = { 0 };
int dp[1001] = { 0 };


int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) 
		cin >> arr[i];
	
	for (int i = 1; i <= n; i++) {
		int maxed = 0,maxed_index=0;
		for (int j = i - 1; j >= 1; j--) {
			if (arr[j] < arr[i] && maxed < dp[j] )
				maxed = dp[j], maxed_index = j;
		}
		dp[i] = arr[i] + dp[maxed_index];
		if (result < dp[i]) result = dp[i];
	}

	cout << result << endl;
}

쉬운 dp 문제입니다.

P(1)부터 P(11)까지 첫 11개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16 ... 

 dp[n] = dp[n-1] + dp[n-5] 라는 점화식을 찾을 수 있게 됩니다.

정답률이 30%대라는게 믿기지 않을 정도로 쉬워서 의아하며, 

ㅋㅋㅋㅋㅋㅋㅋㅋ

한번 틀렸습니다. 숫자가 증가함에 따라 기하급수적으로 수가 커지는거를 신경못썻습니다. 

int형은 4byte = 32bit = 2의 32승

즉 2,147,483,648x2 만큼의 수를 저장할 수 있습니다.

음수,0양수 모두를 포함해야하기 때문에 아래 표와 같은 범위의 수를 표현할 수 있게 됩니다.

수가 넘어갈때는 제일 아래의 음수값 - 2,147,483,648로 내려가 1씩 올라가며 출력을 하는 구조입니다.

저는 c++에서 long long 형을 사용하여 문제를 해결하였습니다. 

정답코드

#include <iostream>
using namespace std;

long long dp[101] = { 0 };
int t = 0, n;
int main() {
	dp[1] = 1, dp[2] = 1, dp[3] = 1, dp[4] = 2;
	for (int i = 5; i <= 100; i++)
		dp[i] = dp[i - 1] + dp[i - 5];

	cin >> t;

	while (t--) {
		cin >> n;
		cout << dp[n] << endl;
	}
}

실패코드를 먼저 보여드립니다.

#include <iostream>
#include <cmath>
using namespace std;
int dp[100001] = { 0 };

int main() {
	int n = 0;
	cin >> n;
	dp[0] = 0, dp[1] = 1, dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		int num = pow(i,0.5);
		dp[i] = 1 + dp[i - num*num];
		cout << dp[i] << endl;
	}
	cout << dp[n] << endl;
}

반례가 있습니다.

12 = 3*2 + 1 + 1 + 1 = 4

12 = 2*2 + 2*2 + 2*2 = 3

명백하게 그리디적인 관점에서 문제를 해결나갈 수 없는 것을 보실 수 있습니다.

즉, 제곱값이 자신보다 작은 모든 제곱근들에서의 경우의 수를 비교해주어 결과값을 도출하여야 하는 문제입니다. 

#include <iostream>
#include <cmath>
using namespace std;
int dp[100001] = { 0 };

int main() {
	int n = 0;
	cin >> n;
	dp[0] = 0, dp[1] = 1, dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		int num = pow(i,0.5);
		dp[i] = 1 + dp[i - num*num];
		for (int j = num-1; j >= 1; j--) {
			if( (1 + dp[i - j*j]) < dp[i] )
				dp[i] = 1 + dp[i - j*j];
		}
	}
	cout << dp[n] << endl;
}

전형적인 dp문제입니다.

점화식을 고려할때 머리로 연상되지 않습니다.

표를 그리며 차근차근 풀어나가보았습니다.  

예시입력에 경우
        k   0   1   2   3   4   5   6   7   8   9   10
c(0)    [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)    [1] 1   1   1   1   1   1   1   1   1   1   1
c(2)    [2] 1   1   2   2   3   3   4   4   5   5   6
c(3)    [5] 1   1   2   2   3   4   5   6   7   8   10

1의 경우에는 모두 1가지 경우의수를 가지게 되고

2를 포함할 경우 2의 배수마다 경우가 한가지씩 증가하는 것을 확인 할 수 있었습니다.

즉, 2를 포함할 때 1의 경우+ DP[N-2] + 1 의 경우가 됨을 확인할 수 있습니다. 

5를 포함할 때에는 (1의경우가 포함된) 2의 경우 + DP[N-5] + 1 이 됨을 확인할 수 있었습니다. 

즉 점화식을 나타내면 

for (int i = 0; i < n; i++) {
		dp[i][0] = 1;
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num&& i>0) dp[i][j] = dp[i][j - num] + dp[i - 1][j];
			else if(i>0) dp[i][j] = dp[i - 1][j];
			else if (j >= num) dp[0][j] = dp[i][j - num];
		}

	}

네 메모리 초과입니다.. :) ㅋㅋㅋ

문제조건이 4MB였네요. 

int형은 4byte이고 n=100까지, k=10000까지이니 dp 2차원 배열은 4000,000byte= 4000kbyte = 4mbyte이므로 메모리 초과가 나는것입니다. 직관적으로 점화식이 변화하는것을 확인했기때문에 dp[101][10001] 를 dp[10001]로 줄여보겠습니다. 

	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num) dp[j] += dp[j - num] ;
		}
	}

전체코드입니다. 

#include <iostream>

using namespace std;

int dp[10001] = { 0 };
int n = 0, k = 0;
int arr[100] = { 0 };
int result = 0;

int main() {

	cin >> n >> k;
	
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num) dp[j] += dp[j - num];
		}

	}
	cout << dp[k] << endl;
}

시뮬레이션 문제같은 경우에는 미리 청사진을 자세하게 그려놓고 문제를 풀이하는게 중요합니다.

문제에서 요구하는 조건을 꼼꼼히 확인하고 단계별로 코딩을 하면 쉽게 풀 수 있는 문제였습니다. 

주석하는 습관, 디버깅습관을 기를 수 있는 좋은 문제입니다.

// 동 서 남 북 1 2 3 4
/*
 1. 이동할 수 있는 구간인지 확인하고 불가능하면 continue로 이동하지말구 나가기  O
 2. 좌표변경 후, 이동할 수 있으면 주사위 쉐이킹 O
 3. 바닥이 0이면 바닥에 주사위의 해당수를 넣기 O
 4. 바닥이 0이 아니면 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여 있는 수는 0이 된다. O
 5. 윗면 dice[1]을 출력한다. O
*/
#include <iostream>
using namespace std;

int n, m, x, y, k;
int arr[21][21] = { 0 };
int karr[1000] = { 0 };
int dice[7] = { 0, }; // 인덱스 순서대로 값을 나타내는것  6번째가 항상 아래가 되는 구조인거지 

void verifydice(int direction) {
	int temp = 0;

	if (direction == 1) {
		temp = dice[6];
		dice[6] = dice[3];
		dice[3] = dice[1];
		dice[1] = dice[4];
		dice[4] = temp;
		// 2랑 5는 동일한 구조
	}
	else if (direction == 2) {
		temp = dice[6];
		dice[6] = dice[4];
		dice[4] = dice[1];
		dice[1] = dice[3];
		dice[3] = temp;
		// 2랑 5는 동일한 구조
	}
	else if (direction == 3) {
		temp = dice[6];
		dice[6] = dice[5];
		dice[5] = dice[1];
		dice[1] = dice[2];
		dice[2] = temp;
		// 3랑 4는 동일한 구조
	}
	else if (direction == 4) {
		temp = dice[6];
		dice[6] = dice[2];
		dice[2] = dice[1];
		dice[1] = dice[5];
		dice[5] = temp;
		// 3랑 4는 동일한 구조
	}

}

int main() {

	cin >> n >> m >> x >> y >> k; //입력1  (x,y)

	for (int i = 0; i < n; i++) //입력2
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];

	for (int i = 0; i < k; i++) //입력3
		cin >> karr[i];


	for (int s = 0; s < k; s++) { // k번 만큼 횟수

		if (karr[s] == 1) { // 동쪽으로 이동할때 
			if ((y + 1) >= m)
				continue;
			y++;
			verifydice(1);

		}
		else if (karr[s] == 2) { //서쪽으로 이동할때 
			if ((y - 1) < 0)
				continue;
			y--;
			verifydice(2);

		}
		else if (karr[s] == 4) { //남쪽으로 이동할때 
			if ((x + 1) >= n)
				continue;
			x++;
			verifydice(3);

		}
		else if (karr[s] == 3) { //북쪽으로 이동할때 
			if ((x - 1) < 0)
				continue;
			x--;
			verifydice(4);
		}

		//3,4번의 기능을 구현 
		if (arr[x][y] == 0)
			arr[x][y] = dice[6];
		else {
			dice[6] = arr[x][y];
			arr[x][y] = 0;
		}
		//5번
		cout << dice[1] << endl;
	}


}

시뮬레이션 문제같은 경우에는 미리 청사진을 자세하게 그려놓고 문제를 풀이하는게 중요합니다.

문제에서 요구하는 조건을 꼼꼼히 확인하고 단계별로 코딩을 하면 쉽게 풀 수 있는 문제였습니다. 

주석하는 습관, 디버깅습관을 기를 수 있는 좋은 문제입니다.

/*
1. 값 입력받기  ok
2. 현재 방향에 따라 뱀 이동시키기 (이동규칙 3가지는 문제 참조)  ok
	4방향으로 구분, 사과가 있을때와 사과가 없을때로 구분 ok
3. 이때 벽이거나 자기에게 닿으면 종료  ok
4. 방향전환을 해야하는지 확인 ok

*/

#include <iostream>
using namespace std;
typedef struct snaketurn
{
	int x;
	char c;
}snaketurn;

int n, k,l;
int arr[101][101] = { 0, };
int yy, xx; //입력을 위한 

snaketurn turned[100];
int snakeEnd = 0; //  X가 증가하는 순으로 주어지니까 포인터를 만든 것
int sec = 0, currentDirection = 1;

int snake[101][2] = { 0, }; //뱀의 좌표를 저장해둘 공간들  행, 열 순
int snakePointer = 0;

int lasty = 0, lastx = 0;

void modify();
void changedirection();
int main() {
	cin >> n;
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> yy >> xx;
		arr[yy][xx] = 1;
	}
	cin >> l;
	for (int i = 0; i < l; i++)
		cin >> turned[i].x >> turned[i].c;
	//1
	snake[0][0] = 1, snake[0][1] = 1; //처음에 뱀의 위치를 지정 

	while (1) {
		bool jud = false;
		sec++;
		modify(); //2
		// ------------------3----------------------
		if (snake[0][0]<1 || snake[0][1]<1 || snake[0][0]>n || snake[0][1]>n) //벽에 부딪힐때 
			break;
		for (int i = 1; i <= snakePointer; i++) { //자기 자신한테 부딪히는지 확인 
			if (snake[0][0] == snake[i][0] && snake[0][1] == snake[i][1]) {
				jud = true;
				break;
			}
		}
		if (jud == true)
			break;

		if (lastx == snake[0][1] && lasty == snake[0][0])
			break;
		//--------------------4------------------
		changedirection(); //4
	}
	cout << sec << endl;
}



void modify() {
	lasty = snake[snakePointer][0], lastx = snake[snakePointer][1];
	if (currentDirection == 1) { //오른쪽 방향 
		if (arr[snake[0][0]][snake[0][1] + 1] == 1) {//이동할 공간에 사과가 있다면 
			arr[snake[0][0]][snake[0][1] + 1] = 0; //0으로 초기화 
			snakePointer++;
			for (int i = snakePointer; i > 0; i--) {
				snake[i][0] = snake[i - 1][0];
				snake[i][1] = snake[i - 1][1];
			}
			snake[0][1] = snake[0][1] + 1; //오른쪽으로 한방향 이동 

		}
		else { //사과가 없을때 
			for (int i = snakePointer; i > 0; i--) {
				snake[i][0] = snake[i - 1][0];
				snake[i][1] = snake[i - 1][1];
			}
			snake[0][1] = snake[0][1] + 1; //오른쪽으로 한방향 이동 
		}
	}




	else if (currentDirection == 2) { //아래방향
		if (arr[snake[0][0] + 1][snake[0][1]] == 1) {//이동할 공간에 사과가 있다면 
			arr[snake[0][0] + 1][snake[0][1]] = 0;
			snakePointer++;
			for (int i = snakePointer; i > 0; i--) {
				snake[i][0] = snake[i - 1][0];
				snake[i][1] = snake[i - 1][1];
			}
			snake[0][0] = snake[0][0] + 1; //아래로 한칸이동
		}
		else { //사과가 없을때 
			for (int i = snakePointer; i > 0; i--) {
				snake[i][0] = snake[i - 1][0];
				snake[i][1] = snake[i - 1][1];
			}
			snake[0][0] = snake[0][0] + 1; //아래로 한칸이동 
		}
	}


	else if (currentDirection == 3) { //왼쪽 방향
		if (arr[snake[0][0]][snake[0][1] - 1] == 1) {//이동할 공간에 사과가 있다면 
			arr[snake[0][0]][snake[0][1] - 1] = 0; //0으로 초기화 
			snakePointer++;
			for (int i = snakePointer; i > 0; i--) {
				snake[i][0] = snake[i - 1][0];
				snake[i][1] = snake[i - 1][1];
			}
			snake[0][1] = snake[0][1] - 1; //오른쪽으로 한방향 이동 
		}
		else { //사과가 없을때 
			for (int i = snakePointer; i > 0; i--) {
				snake[i][0] = snake[i - 1][0];
				snake[i][1] = snake[i - 1][1];
			}
			snake[0][1] = snake[0][1] - 1; //오른쪽으로 한방향 이동 
		}

	}
	else if (currentDirection == 4) {  //위로 이동하는경우 
		if (arr[snake[0][0] - 1][snake[0][1]] == 1) {//이동할 공간에 사과가 있다면 
			arr[snake[0][0] - 1][snake[0][1]] = 0;
			snakePointer++;
			for (int i = snakePointer; i > 0; i--) {
				snake[i][0] = snake[i - 1][0];
				snake[i][1] = snake[i - 1][1];
			}
			snake[0][0] = snake[0][0] - 1; //아래로 한칸이동
		}
		else { //사과가 없을때 
			for (int i = snakePointer; i > 0; i--) {
				snake[i][0] = snake[i - 1][0];
				snake[i][1] = snake[i - 1][1];
			}
			snake[0][0] = snake[0][0] - 1; //아래로 한칸이동 
		}
	}




}


void changedirection() {

	if (turned[snakeEnd].x == sec) {
		if (currentDirection == 1) {
			if (turned[snakeEnd].c == 'D')
				currentDirection = 2;
			else
				currentDirection = 4;
		}
		else if (currentDirection == 2) {
			if (turned[snakeEnd].c == 'D')
				currentDirection = 3;
			else
				currentDirection = 1;
		}
		else if (currentDirection == 3) {
			if (turned[snakeEnd].c == 'D')
				currentDirection = 4;
			else
				currentDirection = 2;
		}
		else if (currentDirection == 4) {
			if (turned[snakeEnd].c == 'D')
				currentDirection = 1;
			else
				currentDirection = 3;
		}

		snakeEnd++;
	}

}