글 읽기 - 잘못 생각한건가요?

2468ab 6년 전 0

제생각에 숫자가 100만까지이니 배열을 100만짜리를 만들어서 입력을 받은후

삼각형의 변의길이중에 중간값을 정합니다 중간값이 정해지면 가장큰값과 가장 작은 값이 정해지니까요

1 2 3 4 5 6 7 8 이라는 길이가 있으면

5가 삼각형의 변의 길이중 중간값이라고 하면 작은 길이는 1 2 3 4 가 될수 있고 큰 길이는 6 7 8 이 될수 있습니다 이때

가장 작은 변의 길이는 1 2 3 4 중 가장 큰 값이 설정되어야 합니다 왜나하면 가장 작은값으로 만들수있는 길이를 가장 큰값으로도 만들수 있기 떄문이죠 그런데 문제의 조건이 둘레가 가장 커져야 하니 이값은 삼각형 변의 중간값보다 작은 값중에 가장 큰 값이라고 생각합니다

그후 가장 큰값을 정해 답을 도출해 나갔는데 뭐가 잘못된걸까요?

#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{
	int number, max_sum = -1,cnt = 0;
	int min = 1000000, max = 0;
	bool length[1000001] = { 0, };
	int data[1000001];
	cin >> number;                      // 갯수 입력
	for (int i = 0; i < number; i++)
	{
		int input;                     
		cin >> input;                    // 값 입력
		length[input] = 1;               // 100만 크기의 배열에 저장
		if (input >= max)                // input 값의 max값 min값 저장
		{
			max = input;
		}
		if (input <= min)
		{
			min = input;
		}
	}
	for (int i = min; i <= max; i++)    // 100만 배열을 보면서 sort된 길이값 저장
	{
		if (length[i] == 1)
		{
			cnt = cnt + 1;
			data[cnt] = i;
		}
	}
	for (int i = cnt-1; i >= 2; i--)  // i 는 길이의 중간값이라고 생각하고 작은길이 큰길이를 찾음
	{
		int sum2 = data[i] + data[i-1];
		if (sum2 > data[i + 1])
		{
			for (int j = cnt; j >= i + 1; j--)
			{
				if (sum2 > data[j])
				{
					max_sum = sum2 + data[j];
					break;
				}
			}
			break;
		}
	}
	cout << max_sum;
}

jh05013 6년 전 0

빨대의 길이가 중복될 수도 있습니다.

시간초과가 나올 수도 있을 것 같은데, break가 있어서 확실치는 않네요.

2468ab 6년 전 0

아 길이가 중복될 수 있는걸 간과했네요. 감사합니다.

시간초과는 break 때문에 안날거같아요.

2468ab 6년 전 0

감사합니다 해결했습니다.

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

문제

문제

출처

ICPC

잘못 생각한건가요?

2468ab 6년 전 0

jh05013 6년 전 0

2468ab 6년 전 0

2468ab 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말