BOJ : 12845

💡문제 분석 요약

그리디 알고리즘 문제로 거의 공식만 찾으면 된다. 가장 큰 값을 가진수는 자신과 더해지는 것 빼고 다 더하고 나머지 값들은 그냥 결과값에 한번씩 추가해주면 된다.

💡알고리즘 설계

1. 카드의 개수 입력받기
2. 카드들을 배열에 저장
3. for문을 통해 result값에 모든 값들을 더해주기
4. 가장 큰 수 Math.max 활용하여 찾기
5. max*(N-2) 더해주기

💡코드

package week6;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q12845_boj {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int arr[] = new int[N];
        int max = 0, result = 0;

        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0;i<arr.length;i++){
            result += arr[i];
            max = Math.max(max, arr[i]);
        }

        result += max*(N-2);

        System.out.println(result);
    }
}

💡시간복잡도

O(N)

입력받은 N만큼만 연산함

💡 틀린 이유

ㅋ

💡 틀린 부분 수정 or 다른 풀이

• 다른 풀이알고리즘 같음

package week01;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Marble_12845{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());	// 카드의 개수를 입력받는다
		String[] arr = br.readLine().split(" ");	// 입력받은 레벨을 나누어서 배열로 저장
		
		int i;
		int max = 0, sum = 0;
		for(i=0; i<n; i++) {
			int L = Integer.parseInt(arr[i]);	// String으로 저장된 레벨을 int로 변환해준다
			
			// 최대값을 가진 카드(max)와 다른 카드를 합치면 레벨이 작은 카드는 사라진다.
			// 따라서 max를 제외한 모든 카드는 한번씩만 더해지고
			// 이어서 max카드를 max가 다른 카드와 맺을 관계의 수(n-1) 만큼 더한다면 답(result)이 된다.
			// 이 result는 결국 max를 포함한 모든 카드를 한번씩 다 더하고 max를 (n-2)만큼 더한 값과 같다.
			
			sum += L;	// 모든 카드 레벨의 합을 구한다
			
			if(max < L) {
				max = L;	// 레벨 중 최대값을 구한다
			}
		}
		
		int result = sum + (max*(n-2));
		System.out.println(result);
	}
	
}

💡 느낀점 or 기억할정보

그리디 알고리즘 같은 경우 공식만 찾으면 간단 초간단티비