[Java] SWEA View & 최대 상금

1206 View 문제 링크

#1

15분

import java.util.HashMap;
import java.util.Scanner;
import java.io.FileInputStream;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=10;

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = sc.nextInt();
            int[] arr = new int[N];
            for(int i=0; i<N; i++) {
                arr[i] = sc.nextInt();
            }

            int max = 0;
            int result = 0;
            for(int j=2; j<N-2; j++) {
                max = Math.max(arr[j-2], Math.max(arr[j-1], Math.max(arr[j+1], arr[j+2])));
                result += Math.max(arr[j] - max, 0);
            }
            System.out.println("#"+test_case+" "+result);
        }
    }
}

1244 최대 상금 문제 링크

#1

50분

import java.util.HashMap;
import java.util.Scanner;
import java.io.FileInputStream;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            String N = sc.next();
            char[] arrN = new char[N.length()];
            for(int i=0; i<N.length(); i++) {
                arrN[i] = N.charAt(i);
            }
            int C = sc.nextInt();
            C = Math.min(C, N.length());
            int result = dfs(arrN, 0, C, 0);

            System.out.println("#"+test_case+" "+result);
        }
    }

    static int dfs(char[] arrN, int level, int C, int max) {
        if(level==C) {
            String result = "";
            for(int i=0; i<arrN.length; i++) {
                result += arrN[i];
            }
            return Integer.parseInt(result);
        }

        char a;
        for(int i=0; i<arrN.length; i++) {
            for(int j=i+1; j<arrN.length; j++) {
                a = arrN[i];
                arrN[i] = arrN[j];
                arrN[j] = a;

                max = Math.max(dfs(arrN, level+1, C, max), max);
                // 각 단계마다 모든 swap의 경우를 구해서 max를 갱신

                a = arrN[i];
                arrN[i] = arrN[j];
                arrN[j] = a; // 빽트래킹으로 원본값 유지
            }
        }

        return max;
    }
}

• 완전 탐색으로 하면 시간초과가 날 것 같아서 계속 고민 했는데
• 그것말고 방법이 없어보임..
• 그래서 일단 했는데 역시나 시간초과
  
  
• dfs로 하되 N의 길이만큼 자리 교환을 하면 최댓값을 구하는 것과 같음
• 그래서 C와 N의 길이를 비교해서 C가 더 크면 길이만큼 돌림
  
  
  
• 맞긴 했는데
• 주석 달다가 생각났는데

1
94 3

• 인 경우에 결과가 49가 나와야 되는데
• 해당 코드는 94가 나옴
• 테스트 케이스 부족으로 오류가 있는 문제인 듯..?