프로그램 명: paper
점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한번에 자른다.
예를 들어, 그림의 가로 길이 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;
}
'c·c++ > c 프로그래밍' 카테고리의 다른 글
산길 내려가는 경로찾기 (0) | 2013.05.04 |
---|---|
스캐너(token으로 쪼개기) (0) | 2013.05.03 |
1부터 1000까지 3,6,9 의 숫자가 들어가는 소수들의 합을 구하는 문제 (0) | 2013.05.01 |
0과 1사이의 기약분수 (0) | 2013.04.28 |
floor, ceil 함수 (0) | 2013.04.20 |