[정올] - [1067]종이자르기

종이자르기 Time Limit : 1000MS   아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다. 점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이 때 가장 큰 종이 조각의 넓이는 30㎠이다. 입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오. 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다. 첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다. 10 8 3 0 3 1 4 0 2 30

출처 : 2001 KOI 초등부 1번

 

 

 

#include<stdio.h>
#include<stdlib.h>

int Proc()
{
	int CutCount = 0;	⁄⁄종이를 자를 횟수 카운트
	int HMax = 0;		⁄⁄종이의 세로 길이
	int WMax = 0;		⁄⁄종이의 가로 길이
	int HWCheck = 0;	⁄⁄가로,세로 컷팅 방향 정하는 flag
	int CutPoint = 0;	⁄⁄자르는 지점
	int Hlenght = 0;	⁄⁄세로의 가장 큰 길이
	int wlenght = 0;	⁄⁄가로의 가장 큰 길이
	int result = 0;		⁄⁄가장 넓은 면적

	FILE *fd;

	fd = fopen("input.txt", "r");

	fscanf(fd, "%d %d\n", &WMax, &HMax);
	fscanf(fd, "%d\n", &CutCount);

	⁄⁄동적 배열을 사용하면 종이의 크기가 변해도 상관 없다.
	int *height = (int*)malloc(sizeof(int)*(HMax+1));	⁄⁄자를 지점 저장 동적배열. (세로)
	int *width = (int*)malloc(sizeof(int)*(WMax+1));	⁄⁄자를 지점 저장 동적배열. (가로)

	height[HMax]=1;	⁄⁄종이의 끝을 표시 (세로)
	width[WMax]=1;	⁄⁄종이의 끝을 표시 (가로)

	for(int i=0; i<CutCount+1; i++)
	{
		fscanf(fd, "%d %d\n", &HWCheck, &CutPoint);
		
		if(HWCheck==0)
		{
			height[CutPoint]=1;
		}
		else if(HWCheck==1)
		{
			width[CutPoint]=1;
		}
	}

	CutPoint=0;  ⁄⁄자르기 시작 할 지점 초기화

	for(int i=1; i<(HMax+1); i++)
	{
		if(height[i]==1)
		{
			if(Hlenght<(i-CutPoint))	⁄⁄이전의 자른 길이와 지금 자른 길이를 비교. (세로)
				Hlenght=(i-CutPoint);
			CutPoint=i;		⁄⁄자른 지점을 저장
		}
	}

	for(int i=1; i<(WMax+1); i++)
	{
		if(width[i]==1)
		{
			if(wlenght<(i-CutPoint))	⁄⁄이전의 자른 길이와 지금 자른 길이를 비교. (가로)
				wlenght=(i-CutPoint);
			CutPoint=i;		⁄⁄자른 지점을 저장
		}
	}

	free(height);	⁄⁄동적 배열 해제
	free(width);	⁄⁄동적 배열 해제

	fclose(fd);

	return wlenght*Hlenght;
}

void output(int result)
{
	FILE *fd;

	fd = fopen("output.txt", "w");

	fprintf(fd,"%d", result);

	fclose(fd);
}

void main(void)
{
	int s = Proc();

	output(s);
}