글 읽기 - 어떤 부분을 수정해야 할까요?

kmsun9941 6년 전 0

sArr[one]의 값이 0보다 크면 바로 이전까지의 수를 가져오고

(sArr[one-1])*10 + sArr[one]의 값이 10이상 26이하일 경우에는 이전 두자리까지의 수를 추가로 더하면서 값을 구하고자하는데 답이 틀리게 나옵니다.

어떤 부분을 수정해야 하나요?

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		String s = sc.next();
		int size = s.length();
		
		char [] sArr = new char [size+1];
		for(int i=1; i<=size; i++)
			sArr[i] = s.charAt(i-1);
		
		int [] dp = new int [size+1];
		dp[0] = 1;
		dp[1] = 1;
		
		for(int i=2; i<=size; i++) {
			int one = i-1;
			if(sArr[one] > '0')
				dp[i] = dp[i-1] % 1000000;
			
			int two = (sArr[one-1]-'0')*10 + sArr[one]-'0';
			if(10<=two && two<=26)
				dp[i] = (dp[i]+dp[i-2]) % 1000000;
		}
		
		System.out.println(dp[size]);
	}
}

isangyoon 6년 전 0

굳이 String을 Array로 바꾸실 필요가 없다고 생각하며 (불필요한 연산)

다음과 같이 수정하시면 AC됩니다. DP 점화식 자체는 틀린게 없고 코딩 문제로 보이네요.

import java.util.Scanner;
  
public class Main
{ 
    public static void main(String[] args)
    {
      Scanner scanner = new Scanner(System.in);
         
      String string = scanner.next();
      int length = string.length();
       
      int[] dp = new int[length + 10];
      dp[0] = dp[1] = 1;
         
      for(int i = 2; i <= length; i++)
      {
        int one = string.charAt(i - 1) - '0';
        if (one > 0) dp[i] = dp[i - 1] % 1000000;
         
        int two = (string.charAt(i - 2) - '0') * 10 + (string.charAt(i - 1) - '0');
        if (two >= 10 && two <= 26) dp[i] = (dp[i] + dp[i - 2]) % 1000000;
      }
         
      System.out.println(dp[length]);
    }
}

isangyoon 6년 전 0

덧붙여서, String을 Char Array로 변환시켜주는 메소드도 제공하고 있습니다.

https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#toCharArray--

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

문제

문제

출처

ICPC

어떤 부분을 수정해야 할까요?

kmsun9941 6년 전 0

isangyoon 6년 전 0

isangyoon 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말