c·c++/c 프로그래밍

paper자르기

바로이순간 2013. 5. 2. 11:40

프로그램 명: paper

제한시간: 1 초

그림과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로 방향과 세로 방향으로 1 마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1 번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다.

점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한번에 자른다.

예를 들어, 그림의 가로 길이 10 이고 세로 길이 8 인 종이를 3 번 가로 점선, 4번 세로 점선, 그리고 2 번 가로 점선을 따라 자르면 그림과 같이 여러 개의 종이 조각으로 나뉘게 된다. 이 때 가장 큰 종이 조각의 넓이는 30 이다.

입력으로 종이의 가로와 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 인지를 구하는 프로그램을 작성하시오.

프로그램의 실행시간은 1초를 넘을 수 없다.

입력 형식

  • 첫째 줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100 이다.
  • 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다.
  • 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0 과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1 과 점선 번호가 주어진다.입력되는 두 숫자 사이에는 빈칸이 하나씩 있다.

출력 형식

첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다.

입출력 예

입력
10 8
3
0 3
1 4
0 2
출력
 

30


#include <stdio.h>

int main() {

    int garo[100]={0,}; // 가로 방향

    int sero[100]={0,};  // 세로 방향

    // szg: 가로의 크기  szs: 세로의 크기

    // n: 입력의 갯수

    int szg, szs, n;

    // ig: 가로의 인덱스, is: 세로의 인덱스

    int i, j, x, y, ig, is;

    // mg: 최대 가로,   ms: 최대 세로

    int mg, ms;

    // 가로의 크기와 세로의 크기를 입력받는다.

    scanf("%d%d", &szg, &szs);

    // 자르는 갯수를 입력받는다.

    scanf("%d", &n);

    // 자른 선을 garo나 sero에 삽입을 한다.

    // 현재는 0과 가로의 크기, 0과 세로의 크기가 들어있다.

    garo[0]=0;

    garo[1]=szg;

    sero[0]=0;

    sero[1]=szs;

    ig=2;  // 가로 인덱스

    is=2;  // 세로 인덱스

    for(i=0;i<n;++i) {  // 갯수만큼 입력을 받는다.

        scanf("%d%d", &x, &y);  // 구분은 x에 번호는 y에 입력을 받는다.

        if(x==0) {  // 가로로 자르면 세로가 분할된다.

            sero[is]=y;  // sero에 번호를 추가한다.

            is+=1;           // 세로 인덱스를 증가시킨다.

        } else {  // 세로로 자르면 가로가 분할된다.

            garo[ig]=y;  //garo에 번호를 추가한다.

            ig+=1;           // 가로 인덱스를 증가시킨다.

        }

    }

    // 가로를 정렬한다. - 삽입정렬

    for(i=1;i<ig;++i) {

        x=garo[i];

        j=i;

        while(j>0 && garo[j-1]>x) {

            garo[j]=garo[j-1];

            j-=1;

        }

        garo[j]=x;

    }

    // 세로를 정렬한다. - 삽입정렬

    for(i=1;i<is;++i) {

        x=sero[i];

        j=i;

        while(j>0 && sero[j-1]>x) {

            sero[j]=sero[j-1];

            j-=1;

        }

        sero[j]=x;

    }

    // 가로의 최대 부분을 찾는다.

    x=0; // 최대값을 0으로 출발한다.

    for(i=1;i<ig;++i) {

        y=garo[i]-garo[i-1]; // 붙어 있는 두 번호의 차이가 선분의 길이이다.

        if(y>x) x=y; // 선분의 길이가 x보다 크다면 x의 값을 바꾸어 준다.

    }

    mg=x; // 최대 가로를 구하였다.

    // 세로의 최대 부분을 찾는다.

    x=0; // 최대값을 0으로 출발한다.

    for(i=1;i<is;++i) {

        y=sero[i]-sero[i-1]; // 붙어 있는 두 번호의 차이가 선분의 길이이다.

        if(y>x) x=y; // 선분의 길이가 x보다 크다면 x의 값을 바꾸어 준다.

    }

    ms=x; // 최대 세로를 구하였다.

    // 최대면적은 최대 가로 곱하기 최대 세로이다.

    printf("%d\n", mg*ms);


    return 0;

}