글 읽기 - 아무리 봐도 틀린 이유를 모르겠습니다.

jack8226 3년 전 0

예시로 나와 있는 경우는 모두 맞았고 구글링해서 맞는 코드를 찾아다가 입출력도 비교해보고 계산 논리도 비교해봤습니다. 일단 입출력은 모두 맞았고 제 뇌로는 계산 방법도 크게 다르지 않은 것 같은데 자꾸 틀렸다고 뜨네요.

해당 코드에 대한 내용은 주석으로 처리했습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
	int number;
	scanf("%d", &number);		//N 입력
	vector<int> arr(number);	//배열
	for (int i = 0; i < number; i++)
	{
		scanf("%d", &arr[i]);	//배열 입력
	}
	if (number == 2)		//N == 2 일 경우, 가장 큰 수가 답이다.
	{
		printf("%d", (arr[0] >= arr[1]) ? arr[0] : arr[1]);
		return 0;
	}
	/*
		2가지 방법을 사용한다.  첫번째는 가장 작은 두 숫자의 차가 큰 경우다.
		가령 N == 4 이고 다른 입력이 1,100,101,102 같은 경우다. 
		이와 같은 경우는 가장 작은 숫자인 1이 다른 숫자를 대리고 2차례 왕복,마지막은 한번만 이동 
		하므로 100+101+102+2이다.
	
		다른 방법은 가장 작은 두 숫자의 차가 그리 크지 않을 때이다.
		이 경우 다음 과정을 반복했다.	왼쪽을 A 진형, 오른쪽을 B 진형이라 하자.
		1. A에서 가장 작은 것 2개 이동
		2. B에서 가장 작은 것 1개 이동
		3. A에서 가장 큰 것 2개 이동
		4. B에서 가장 작은 것 1개 이동
		N이 짝수일 경우, 1번 과정이 끝나고 모든 과정이 끝난다.
		N이 홀수일 경우, 모든 과정이 끝나고 가장 작은 3개의 숫자가 남는다.
		N= 3일 때 min cost 는 a0+a1+a2 이다. 즉 이를 더해준다. (B진형에 a0,a1,a2보다 작은 숫자가 없다.)


		1~4번 과정의 cost 는 다음과 같다.  (arr 는 sort 이후다)
		arr[1] + arr[0] + arr[biggest one] + arr[1]
		arr[biggest one]의 경우, A 진형에 남아있는 숫자중 가장 큰 숫자(sort를 했으니 가장 오른쪽에 있는 숫자)
		이며 해당 자리는 arr[number - 1 - i * 2] 로 구하였다. (한번에 2개씩 옮기므로 i * 2)
		
		이러한 과정은 N이 짝수일 때 N/2 - 1 홀수 일때 (N-1)/2 - 1번 실행 되는데
		이는 (N-2)/2 와 같다.
		N이 짝수일 경우, 1번 과정에서 끝나므로 1번 과정의 cost를 더해줘야된다.
		a2 이 그것이다.
		N이 홀수일 경우, arr[0] + arr[1] + arr[2]를 더해준다.
	
	
	*/
	int result1, result2 = 0;		//result1에는 첫번째 경우, result2 에는 두번째 경우를 저장
	sort(arr.begin(), arr.end());	//arr 를 배열한다.
	result1 = arr[0] * (number - 2);	//가장 작은 숫자가 왕복하며 다른 숫자를 이동시킨다.
	for (int i = 1; i < number; i++)
	{	
		result1 += arr[i];			//다른 숫자는 모두 더해준다.
	}
	int a1 = arr[0], a2 = arr[1];	//자주 쓰이는 가장 작은 숫자 arr[0],arr[1]을 따로 쓴다.
	int time = (number - 2) / 2;	//시행 횟수인 time(1~4까지의 사이클 시행 횟수)
	for (int i = 0; i < time; i++)
	{
		result2 += (a1 + 2 * a2 + arr[number - 1 - i * 2]); //한 사이클당 코스트를 시행 횟수만큼 더해준다.
	}
	if (number % 2 != 0)
	{
		result2 += (a1 + a2 + arr[2]);	//N이 홀수일 경우, a0, a1, a2를 더해준다.
	}
	else
	{
		result2 += a2;			//N이 짝수일 경우 1번 과정의 cost인 a2를 더해준다.
	}
	int result = (result1 < result2) ? result1 : result2;		//result1과 result2 중 더 작은 것을 고른다.
	printf("%d", result);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아무리 봐도 틀린 이유를 모르겠습니다.

jack8226 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말