알고리즘-그리디-곱하기 혹은 더하기

알고리즘-그리디-곱하기 혹은 더하기

 

문제 : 숫자로된 문자 S가 주어졌을때 왼쪽에서 오른쪽으로 숫자 사이에 X 또는 +를 넣어서 만들어 질 수              있는 가장 큰 수를 구하시오

            단, 일반적인 연산과 달리 +,X에는 우선순위가 없습니다.

 

 

            S의 범위는 1~ 20

 

해결방안

         1. S의 범위가 1~20  이면 O(N^3)이하

         2. 가장 큰수를 구하라 했으니 그리디 생각

         3. 현재 결과값이나 다음 숫자가 0 또는 1이 아니라면 곱하기하는 것이 수가 커질것이다.

         4. 처음수를 X , 그 다음수를 Y라 하면 X와 Y중에 0 또는 1이 있다면 더하고 없으면 곱해야한다.

 

 

 

 

코드

 

public static void main(String[] args) throws IOException {

    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String num = bf.readLine();

    int result = 0;
    result = num.charAt(0) - '0';  //첫번째 자리를 대입
    for (int i = 1; i < num.length(); i++) {
        int nownum = num.charAt(i) - '0'; //현재 자리 숫자
        if (nownum <= 1 || result <= 1) {
            result += nownum;
        } else {
            result *= nownum;
        }
    }
    System.out.println(result);