모두의 마블(12845번)

PearLine_Zero·2024년 5월 22일

baekjoon

하루에 1커밋 CodingTest

목록 보기

103/110

티어 : Sliver 3

정답여부 : 오답

알고리즘 유형 : 그리디 알고리즘

시간 제한 : 1초

💡문제

영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다.

이번 이벤트는 다음과 같다. 순서가 매겨진 여러 장의 카드가 있다. 각각의 카드는 저마다 레벨이 있다.

카드 A에 카드 B를 덧붙일 수 있다. 이때 붙이는 조건은 다음과 같다.

두 카드는 인접한 카드여야 한다.
업그레이드 된 카드 A의 레벨은 변하지 않는다.
카드 합성을 할 때마다 두 카드 레벨의 합만큼 골드를 받는다.

영관이가 골드를 최대한 많이 받을 수 있게 여러분이 도와주자.

예를 들어, c1, c2, c3로 연속된 카드 3개가 있고 각각 레벨이 40,30,30 이라고 하자.

이 카드들을 합치는 과정에서, 먼저 c3에 c2를 합쳐 임시 카드 x1을 만든다. x1의 레벨은 30이고 획득 골드는 60이다. 그 다음엔 c1에 x1을 합쳐 카드 x2를 만들면 레벨이 40이고 70만큼의 골드를 획득할 수 있다. 이때, 영관이가 획득한 골드는 70+60 = 130이다.

다른 방법으로 c1에 c2를 덧붙인 카드 x1을 만들면, x1의 레벨은 40이고 획득한 골드는 70이다.

x1에 c3를 덧붙인 카드 x2의 레벨은 40이고 획득 골드는 70이다. 이때, 영관이가 획득한 골드는 70 + 70 = 140이다. 이외에 더 많은 골드를 받는 방법이 없으므로 140이 획득할 수 있는 최대 골드이다.

💡입력

카드의 개수 n(1 ≤ n ≤ 1,000)이 주어진다.

다음 줄에 각각 카드의 레벨 Li가 순서대로 주어진다. (0 < Li ≤ 100,000)

💡출력

영관이가 받을 수 있는 골드의 최댓값을 출력한다.

💡예제 입력 1

3
40 30 30

💡예제 출력 1

3
40 30 30

💡문제요약

카드를 합쳐 가장 큰 골드를 구하면 되는 문제

💡알고리즘 설계

N : 카드 개수

카드 개수를 입력받음
카드 레벨을 입력받음
내림차순으로 정렬
레벨이 높은 카드를 빼주고 for문을 돌려 gold 구해준다.

💡작성코드

Java

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int card[] = new int[N];
		int sum = 0;
		int maxcard = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i< N; i++) {
			card[i] = Integer.parseInt(st.nextToken());
		}
		for (int i = 0; i < N; i++) {
			maxcard = Math.max(maxcard, card[i]);
		}
		for(int i = 0; i < N; i++) {
			if(maxcard != card[i]) {
				sum += maxcard + card[i];
			}	
		}
		System.out.println(sum);
	}	 
}

💡시간복잡도

O(N)

💡틀린 이유 or 수정할 부분

처음 그냥 max의 값을 구하면 되는 문제인줄 알고 풀다가 틀렸다.
생각을 해보니 카드의 규칙이 있다 인근 카드끼리 묶어야 한다는 점
내림차순을 통해 카드 첫번째 위치 배열에 가장 큰 값을 넣고 나머지를 합쳐서 문제를 풀었다.

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

Java

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Integer card[] = new Integer[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i< N; i++) {
			card[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(card, Comparator.reverseOrder());
		int maxcard = card[0];
		int gold = 0;
		for(int i = 1; i < card.length; i++) {
			gold += (maxcard + card[i]);
		}
		System.out.println(gold);	
	}	 
}