글 읽기 - c 반례찾아주세요.

anima0314 1년 전 0

주석단거정도 생각해서 코드짜봤습니다. 채점도 100%갔다가 갑자기 틀렸습니다 떠요.

어떤게 문제일까요?

#include <stdio.h>

// (전체 옷 개수 / 2) >= 가장많은 옷개수이면 됨.
// 가장많은 옷 사이사이에 다른옷을 넣어버리면 되기때문
int main() {
    int N,max=-1; //max = 가장 많은 옷의 개수
	int sum=0;
    scanf("%d",&N);
	int arr[N]={0,};
	for(int i=0;i<N;i++){
		scanf("%d",&arr[i]);
	}
	for(int i=0;i<N;i++){
		max = (arr[i] > max) ? arr[i] : max;
		sum += arr[i];
// sum이 int범위를 벗어나면 가장 많은 옷 개수가 최대 10만개인데
// 전체옷 개수가 20억이 넘으므로 항상 happy이다.
		if(sum<0){
			printf("Happy\n");
			return 0;
		}
	}
	if(sum/2 >= max){
		printf("Happy\n");
	}
	else{
		printf("Unhappy\n");
	}
    return 0;
}

adfsfsf 1년 전 1

10⁵은 100,000이며, 최대 옷의 개수는 10⁵*10⁵으로 10,000,000,000입니다. int 범위는 최대 2,147,483,647으로, 최대 옷 개수는 이것의 약 5배입니다. 즉, 오버플로우가 일어난 후의 값이 max값의 절반보다 작은 양의 값으로 나올 수 있습니다.

wak8835 1년 전 5

안녕하세요. 마지막 저격 케이스 반례는 다음과 같습니다.

- 입력
1
1

- 출력
Unhappy

- 정답
Happy

anima0314 1년 전 1

오버플로우가 나면 한종류의 가장 많은 옷의 개수(max)가 10만개인데 전체옷개수(sum)가 20억이 넘으므로 sum/2 >= max를 만족할 수 밖에 없어서

오버플로우시 남은 계산을 멈추고 happy가 출력된다고 잡았습니다.

anima0314 1년 전 0

1을 전혀 생각못했네요 감사합니다.

adfsfsf 1년 전 2

아, 제가 return 0을 못 봤네요. 잘못된 의견 적어서 죄송합니다.

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

문제

문제

출처

ICPC

c 반례찾아주세요.

anima0314 1년 전 0

adfsfsf 1년 전 1

wak8835 1년 전 5

anima0314 1년 전 1

anima0314 1년 전 0

adfsfsf 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말