BOJ_1239 [ 차트 ]

문제

 

https://www.acmicpc.net/problem/1239

 

 

실패한 이유

문제 조건에서 원의 중심을 지나는 선의 개수의 최댓값을 출력해야되는데

그냥 입력한 순에서 개수를 출력하였습니다. (문제 제대로 꼼꼼히 안봤습니다.)

 

 

 

문제 해결 방법

 

주어진 데이터를 가지고 합해서 정확하게 50이 될 때 이등분선이라고 합니다.

반복문을 돌려서 합이 50이 되는 것을 카운팅 하면 문제를 해결하실 수 있습니다.

여기서 한쪽이 50이되면 반대쪽도 마찬가지로 50이 되므로 카운팅을 한 후 2로 나누어서 출력해주어야 됩니다.

 

 

그리고 아래 예시처럼 2번 같은 경우에는 10 40 50 데이터를 입력받아서 차트를 그린모습입니다.

이 차트 경우에는 반복문을 통해서 충분히 잘나올 수 있지만,

 

1번 차트는 그냥 반복문을 돌리면 제대로 결과가 나올 수 없습니다.

그 이유는 마지막 데이터 40이 처음 입력받은 데이터 10을 더해야 50이 되기 때문입니다.

 

이 문제를 해결하기 위해서 저는 주어진 데이터를 한번더 배열 뒤에다 복사를 해서

2중 반복문을 통해서 이등분선 개수를 구할 수 있습니다. 

카운팅 하는 반복문은 입력한 횟수만큼 돌지만

50이 되도록 더하는 반복문은 배열 크기만큼 돌아서 50이 넘지않을 때까지 모두 더하였습니다. 50이 넘으면 break를 걸었습니다.

 

 

 

그리고 문제에서 주어진 데이터 중에서 선의 개수를 최대로 하고 싶어 하기 때문에 주어진 데이터를 순열을 통해서 모든 케이스를 구해서 최댓값을 출력하였습니다.

 

소스 코드

 

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/Brute%20force/BOJ_1239.cpp