글 읽기 - 엑셀에 직접 적어가면서 규칙을 찾았는데 답은 틀렸다고 나오네요 ㅜㅜ

pty115 7년 전 0

우선 가독성 떨어지는 코드라 죄송합니다ㅜ

1) 1~11을 1~10까지의 수로 표현하는 모든 방법을 구한 후에

2) 그 방법 중 4이상을 포함한 경우를 모두 제외합니다

1) 에서는 D[i] = D[i-1]*2 + 1를 만족하므로,

2-1) 에서 제외할 때도 trim[i] = 1 + trim[i-1]*2를 만족합니다

2-2) 각 경우마다 추가해서 빼주어야 하는 부분은, trim_plus[i] = trim_plus[i-1] + trim_plus[i-2] + trim_plus[i-3]를 만족합니다

4, 7, 10에 대하여, 7, 44, 274로 정답은 출력됩니다

그런데 제출하면 틀렸다고 나옵니다. 빠뜨린 조건이 있거나, 이 조건식이 틀린 것 같습니다

다이나믹을 어설프게 적용하다가 더 복잡한 문제로 변해버렸네요 .... ㅜㅜ

엑셀에는 다음 그림처럼 그렸습니다

import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test_case = sc.nextInt();
		int[] D = new int[12];
		int[] trim = new int[12];
		int[] trim_plus = new int[12];
		
		//D[i] = D[i-1]*2 + 1
		for(int i=1; i<=D.length-1; i++){
			if(i==1 || i==2) D[i] = 1;
			else D[i] = (D[i-1]*2) + 1;
		}
		//(i>7) trim_plus[i] = trim_plus[i-1] + trim_plus[i-2] + trim_plus[i-3]
		for(int i=5; i<=D.length-1; i++){
			if(i<=7) trim_plus[i] = (int)Math.pow(2, i-5);
			else trim_plus[i] = trim_plus[i-1] + trim_plus[i-2] + trim_plus[i-3];
		}
		//(i>4) trim[i] = 1 + trim[i-1]*2 + trim_plus[i]
		for(int i=5; i<=D.length-1; i++){
			if(i==5) trim[i] = 1 + 0 + 1;
			else trim[i] = 1 + trim[i-1]*2 + trim_plus[i];
			D[i] -= trim[i];
		}
		
		for(int tc=1; tc<=test_case; tc++){
			System.out.println(D[sc.nextInt()]);
		}
	}
}

ntopia 7년 전 1

n=2 일 때 답이 틀리는 것 같네요..

pty115 7년 전 0

아아! 그렇네요

2 = 1+1

2 = 2

도 있네요 ㅠ

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

문제

문제

출처

ICPC

엑셀에 직접 적어가면서 규칙을 찾았는데 답은 틀렸다고 나오네요 ㅜㅜ

pty115 7년 전 0

ntopia 7년 전 1

pty115 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말