글 읽기 - 1027 질문입니다.

chatterboy 8년 전 1

예전에 ccw 알고리즘으로 해결이 가능하다고 들어서

ccw로 해결하려고 했지만 계속 틀리네요.. 어디가 잘못되었는지 모르겠네요 ㅠ

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ull;

int N, h[52];

bool ok(int i, int j, int k) {
	ull x1 = i, x2 = j, x3 = k;
	ull y1 = h[i], y2 = h[j], y3 = h[k];
	return x1*y2+x2*y3+x3*y1 < x1*y3+x2*y1+x3*y2;
}

int main() {
	cin>>N;
	for(int i=1; i<=N; ++i) cin>>h[i];

	int ans = 0;

	for(int i=1; i<=N; ++i)
		for(int j=i+1; j<=N; ++j) {
			int a = 1;
			for(int k=i+1; k<j; ++k) {
				if(ok(i, j, k)) {
					a++;
				} else {
					a = 0;
					break;
				}
			}

			ans = max(ans, a);
		}

	cout<<ans;
}

chatterboy 8년 전 0

우선 제 접근법이 틀렸어요. N개 중에서 2개를 뽑아서 그 사이의 수를 구하면 틀리고 i번째 건물에 대해서 왼쪽과 오른쪽 방향 둘 다 고려해서 풀면 해결할 수 있어요!

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

문제

문제

출처

ICPC

1027 질문입니다.

chatterboy 8년 전 1

chatterboy 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말