글 읽기 - 1685 27%에서 틀립니다ㅠ

shdudtjr77 3년 전 0

제가 생각한 풀이는

만약 입력이

1 3 7

이라면

1 ~7까지 초소한의 숫자를 이용한 가짓수를 저장합니다.(이과정에서 만약 제한 갯수를 넘는게 있다면 실행을 중단하고 출력을 해줍니다.)

(dp[1]~dp[7])

다음 부터는

8을 만들기위해서는 dp[1]+1(7)

9 dp[2]+1(7)

....

이와 같은 방식으로 dp[i]=dp[i]+1 점화식을 만들어 for문이 7번 돌면 다시 1에서 시작하며 제한 갯수를 넘는 경우까지 실행을 해줍니다.

이렇게 해결을 하려고 접근하였는데 27%정도에서 틀리네요 ㅠㅠ (숫자의 종류중 음수를 받는 경우도 예외처리 해준 상태입니다.)

고수님들의 답변을 기다리겠습니다.

#include<iostream>
using namespace std;
int value[1001];
int main() {
	int sp,limit;
	cin >> sp;
	int j = 1;
	int x;
	for (int i = 1; i <= sp; i++) {
		cin >> x;
		if (x > 0&&x!=value[j-1]) {
			value[j]=x;
			j++;
		}
	}
	int max = value[j-1];
	int* dp = new int[max+1];
	
	for (int i = 0; i <= max; i++) {
		dp[i] = 0;
		
	}
	cin >> limit;
	bool check = true;
	
	dp[1] = 1;
	int k=1;
	int v = 2;
	for(int i=2;i<=max;i++){
		k = 1;
		while (value[k] <= i&&k<j) {
			k++;
		}
		k--;
		dp[i] = dp[i - value[k]] + 1;

		//cout << i << " 는 " << value[k] << " 에서 멈춤 " << dp[i] << endl;
		if (dp[i] > limit) {
			check = false;
			i = max + 1;
		}
		else {
			v++;
		}
		
	}
	int i;
	while (check) {
		i = 1;
		for (; i <= max; i++) {
			dp[i] = dp[i] + 1;
			//cout << v << " 는 " << value[k] << " 에서 멈춤 " << dp[i] << endl;
			if (dp[i] > limit) {
				check = false;
				i = max + 1;
			}
			else {
				v++;
			}
			
		}
	}
	if (v % 2 == 0) {
		cout << "holsoon win at " << v;
	}
	else {
		cout << "jjaksoon win at " << v;
	}
}

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

문제

문제

출처

ICPC

1685 27%에서 틀립니다ㅠ

shdudtjr77 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말