글 읽기 - 알고리즘 관련 질문

owlsogul 7년 전 0

알고리즘 배운적도 없고 해서 제가 알고 있는 한도내에서 만들어봤는데,

한 팀 i 에 대해서 ai를 A까지의 거리로 두고 bi를 B까지의 거리라 둔 다음,

xi,yi 를 각각 A,B에서 가져올 풍선이라고 하면, yi = 팀에서필요한풍선 - xi라고 표현할수 있어서

거리 구하는 식 aixi + biyi 에 ㄷㅐ입햇어요

그리고 이걸 전체 팀에게 적용해서

(ai-bi)xi + bi*(팀에서 필요한 풍선) 의 나열?된 식을 구했어요

그래서 계수가 작은순으로 풍선을 나눠주면 되겠구나 해서

한번 짜봤는데...

예제는 정답이 나오는데 틀렸다고 하네여 ㅠ

어디가 틀린걸까여ㅛ

#include <stdio.h>

#define MAX 2000

int main() {

	//계산을 편리하게 하기 위한 변수
	int Constant;
	int Coefficient[MAX][2] = { 0 };

	//데이터 저장용 변수
	int NumTeam,      //팀 숫자
		NumBallonAll,     //모든 풍선의 갯수
		NumBallonA,       //A풍선 개수
		NumBallonB,       //B풍선 개수
		ReqAllBallon;     //필요한 모든 풍선의 갯수

	int ReqBallon[MAX] = { 0 },   //팀당 필요한 풍선개수
		DistA[MAX] = { 0 },       //A까지 거리
		DistB[MAX] = { 0 };       //B까지 거리


								  //초기화
	{
		Constant = 0, NumTeam = 0; NumBallonAll = 0; NumBallonA = 0; NumBallonB = 0;
		ReqAllBallon = 0;
	}

	//입력받기
	{
		scanf("%d %d %d", &NumTeam, &NumBallonA, &NumBallonB);
		NumBallonAll = NumBallonA + NumBallonB;
		int i = 0;
		for (i = 0; i < NumTeam + 1; i++) {
			scanf("%d %d %d", &ReqBallon[i], &DistA[i], &DistB[i]);
			Coefficient[i][0] = DistA[i] - DistB[i];
			Coefficient[i][1] = i;
			Constant += DistB[i] * ReqBallon[i];
			ReqAllBallon += ReqBallon[i];
		}
	}

	//버블버블 정렬
	//계수가 작을 수록, B까지 길이가 멀수록 0에 가깝다.
	{
		int tmp, tmp2;
		for (int j = 0; j < NumTeam - 1; j++) {
			for (int i = 0; i < NumTeam - 1; i++) {
				if (Coefficient[i][0] > Coefficient[i + 1][0]) {
					tmp = Coefficient[i][0];
					tmp2 = Coefficient[i][1];
					Coefficient[i][0] = Coefficient[i + 1][0];
					Coefficient[i][1] = Coefficient[i + 1][1];
					Coefficient[i + 1][0] = tmp;
					Coefficient[i + 1][1] = tmp2;
				}
				else if (Coefficient[i][0] == Coefficient[i + 1][0]) {
					if (DistB[Coefficient[i][1]] < DistB[Coefficient[i + 1][1]]) {
						tmp = Coefficient[i][0];
						tmp2 = Coefficient[i][1];
						Coefficient[i][0] = Coefficient[i + 1][0];
						Coefficient[i][1] = Coefficient[i + 1][1];
						Coefficient[i + 1][0] = tmp;
						Coefficient[i + 1][1] = tmp2;
					}
				}
			}
		}
	}

	//나눠주기
	{
		int TeamPointer = 0;
		int Dist = Constant;
		int GivenBallon = 0;
		int WhileExsit = 1;
		while (WhileExsit){
			
			//종료조건
			if (TeamPointer >= MAX - 1 || ReqAllBallon - GivenBallon <= 0) {
				break;
			}

			//나눠주기
			for (int i = 0; i < ReqBallon[Coefficient[TeamPointer][1]]; i++) {
				//음수일 경우
				if (Coefficient[TeamPointer][0] <= 0) {
					//A풍선이 1개 이상 있을 경우
					if (NumBallonA > GivenBallon) {
						Dist += Coefficient[TeamPointer][0];
						GivenBallon++;
					}
					//A풍선이 모자랄 경우 > 종료 (B풍선만 나눠주면 댐)
					else {
						WhileExsit = 0;
						break;
					}
				}
				//양수일 경우
				else {
					//B풍선에서 다 나눠줄수 있는경우 > 종료
					if (NumBallonB >= ReqAllBallon - GivenBallon) {
						WhileExsit = 0;
						break;
					}
					//다 못 나눠주면
					else {
						Dist += Coefficient[TeamPointer][0];
						GivenBallon++;
					}
				}
			}

			//마무리
			TeamPointer++;

		}
		printf("%d", Dist);
	}

	return 0;
}

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

문제

문제

출처

ICPC

알고리즘 관련 질문

owlsogul 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말