알고리즘/백준

[백준] 20300번: 서강근육맨 (JavaScript, NodeJS)

정현수 2022. 1. 20. 20:03
반응형

문제

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.

헬스장에 있는 N개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 10개의 운동기구가 있을 경우 PT를 5번 받으면 모든 기구를 다 사용할 수 있다. 9개의 운동기구가 있는 경우에도 PT를 5번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 M을 넘지 않도록 하고 싶다. 이때, M의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

입력

첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수 N이 주어진다. (1≤N≤10 000)

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 t1,t2,⋯,tN가 주어진다. (0≤ti≤1018)

출력

 M의 최솟값을 출력한다.

예제 입력 1 복사

5
1 2 3 4 5

예제 출력 1 복사

5

PT 첫째 날에 1과 4를 선택하고, 둘째 날에 2와 3을 선택하고, 마지막 날에 5를 선택하면 M은 5가 되며, 이때가 M이 최소일 때이다.

정답 풀이

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; // 리눅스로 테스트할 땐 따로 설정해주어야 합니다.
const input = require("fs").readFileSync(path).toString().trim().split("\n");

let [n, ...loss] = input;
n = +n;
loss = loss[0].split(' ').map(i => BigInt(i));

// 문제 풀이
function solution(n, loss) {
	let answer = 0;
    	loss.sort((a, b) => a < b ? -1 : 1);

	if (loss.length % 2 === 1) {
		answer = loss.pop();
		n -= 1;
	}

	for (let i = 0; i < n / 2; i += 1) {
		const sum = loss[i] + loss[loss.length - 1 - i];
		answer = sum > answer ? sum : answer;
	}

	return answer;
}

// 제출
const answer = solution(n, loss);
console.log(String(answer));
⭐ 문제 핵심 아이디어 ⭐
1. 그리디
2. BigInt

 

상당히 애를 먹은 문제

계속 실패가 나길래 무슨 문제인지 봤더니 N의 범위가 10^18인 것을 보고 자료형 문제인 것을 파악.

 

우선 맨 처음에 입력 받을 때 모든 숫자를 BigInt형으로 받는다.

BigInt는 sort안에서 빼기, 더하기와 같은 연산이 되지 않기 때문에

둘의 대소를 비교해서 정렬을 해준다. (오름차순)

 

배열이 홀수일 때는 제일 큰 값을 answer로 지정해놓고 시작.

 

배열의 길이 / 2 만큼 돌면서

배열의 첫번째와, 마지막 인덱스에서

하나씩 안쪽으로 들어오면서 합을 계산해서 answer과 비교.

 

그리고 마지막에 return할 때 String을 해주어야 오답처리가 안된다.

반응형