글 읽기 - 습격자 초라기 50%에서 막힙니다

ksytwo1541 6년 전 0

아무것도 묶지 않고 dp를 n-1번까지 실행

0번째와 n-1번째 top 을 묶고나서 dp를 n-1번까지 실행 -1

0번째와 n-1번째 bottom 을 묶고나서 dp를 n-1번까지 실행 -1

0번째와 n-1번째 top,bottom 둘다 묶고나서 dp를 n-1번까지 실행 -2

이렇게 했는데 50%에서 실패했습니다가 뜨네요;;

뭐가 잘못됐나요?

#include <iostream>
#include <algorithm>

using namespace std;

int w;	//소대원 수
int n;	//한 원의 방 수
int won[2][10000] = { 0, };	//방에 들어가는 적의 수
int won2[2][2] = { 0, };
int dp[10000][3] = { 0, };
int answer[1000000] = { 0, };


#define INF 10000000

void _dp(int num, int a) {
	int t[4] = { INF,INF,INF,INF };

	switch (a) {
		case 0:

			t[0] = dp[num][2] + 1;
			t[1] = dp[num][1] + 1;
			if (won[0][num] + won[1][num] <= w) {
				t[2] = dp[num - 1][0] + 1;
			}
			else {
				t[2] = dp[num - 1][0] + 2;
			}

			if (won[0][num - 1] + won[0][num] <= w && won[1][num - 1] + won[1][num] <= w) {
				t[3] = dp[num - 2][0] + 2;
			}
			
			dp[num][a] = min(t[0], min(t[1], min(t[2], t[3])));
			break;
	
		case 1:

			if (won[0][num - 1] + won[0][num] <= w) {
				dp[num][a] = dp[num - 1][2] + 1;
	
			} 
			else {
				dp[num][a] = dp[num - 1][0] + 1;
			}
			break;

		case 2:

			if (won[1][num - 1] + won[1][num] <= w) {
				dp[num][a] = dp[num - 1][1] + 1;
			
			}
			else {
				dp[num][a] = dp[num - 1][0] + 1;
			}
			break;

		default:
			break;
	}
		
}


int main() {
	int t; //테스트케이스
	int c[4] = {INF,INF,INF,INF};

	cin >> t;

	for (int k = 0; k < t; k++) {
		cin >> n >> w;
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < n; j++) {
				cin >> won[i][j];
			}
		}
		//임시저장
		won2[0][0] = won[0][0];
		won2[1][0] = won[1][0];
		won2[0][1] = won[0][n - 1];
		won2[1][1] = won[1][n - 1];

		//아무것도 붙지 않은 경우
		if (won[0][0] + won[1][0] <= w) {
			dp[0][0] = 1;
		}
		else {
			dp[0][0] = 2;
		}
		dp[0][1] = 1;
		dp[0][2] = 1;

		for (int i = 1; i < n; i++) {
			_dp(i, 1);
			_dp(i, 2);
			_dp(i, 0);
		}

		c[0] = dp[n - 1][0];

		//0번째 위와 n-1번째 위가 붙은 경우

		if (won[0][0] + won[0][n - 1] <= w && n != 1) {
			won[0][0] = w;
			won[0][n - 1] = w;
			dp[0][0] = 2;
			dp[0][1] = 1;
			dp[0][2] = 1;

			for (int i = 1; i < n; i++) {
				_dp(i, 1);
				_dp(i, 2);
				_dp(i, 0);
			}

			c[1] = dp[n - 1][0] - 1;
		}

		//0번째 아래와 n-1번째 아래가 붙은 경우

		if (won[1][0] + won[1][n - 1] <= w && n != 1) {
			won[0][0] = won2[0][0];
			won[0][n - 1] = won2[0][1];
			won[1][0] = w;
			won[1][n - 1] = w;
			dp[0][0] = 2;
			dp[0][1] = 1;
			dp[0][2] = 1;

			for (int i = 1; i < n; i++) {
				_dp(i, 1);
				_dp(i, 2);
				_dp(i, 0);
			}

			c[2] = dp[n - 1][0] - 1;
		}

		//위아래 둘다 붙은 경우

		if (won[1][0] + won[1][n - 1] <= w && n != 1) {
			won[0][0] = w;
			won[0][n - 1] = w;
			won[1][0] = w;
			won[1][n - 1] = w;
			dp[0][0] = 2;
			dp[0][1] = 1;
			dp[0][2] = 1;

			for (int i = 1; i < n; i++) {
				_dp(i, 1);
				_dp(i, 2);
				_dp(i, 0);
			}

			c[3] = dp[n - 1][0] - 2;
		}

		answer[k] = min(c[0], min(c[1], min(c[2], c[3])));
        
        //여기서부턴 초기화
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 10000; j++) {
				won[i][j] = 0;
			}
		}

		for (int i = 0; i < 10000; i++) {
			for (int j = 0; j < 3; j++) {
				dp[i][j] = 0;
			}
		}

		for (int i = 0; i < 4; i++) {
			c[i] = INF;
		}

	}
    
    //배열에 저장된 답 출력
	for (int i = 0; i < t; i++) {
		cout << answer[i] << endl;
	}

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

습격자 초라기 50%에서 막힙니다

ksytwo1541 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말