2004년 정보올림피아드 전국대회 초등 2번 줄자접기 문제 풀이

오늘 우리 학생 중 한명이 줄자 접기 문제를 설명해 주었는데..

설명에 이해가 안된것 같아서...

줄자접기 문제를 다시 한번 풀어 보겠습니다.

문제)

준성이는 1㎝ 간격으로 눈금이 매겨져 있는 줄자를 가지고 있다. 그 줄자에 있는 서로 다른 눈금 6개에 한 눈금에 하나씩 점이 찍혀 있는데, 빨간 점, 파란 점, 노란 점이 각각 두 개씩 있다.   준성이는 먼저 빨간 점이 만나도록 줄자를 접었다. 그런 후 두 파란 점이 만나도록 줄자를 접고, 또 다시 두 노란 점이 만나도록 줄자를 접었다. 줄자는 투명하여 접더라도 점들을 잘 볼 수 있다. 어떤 색깔의 두 점이 만나도록 줄자를 접었을 때, 그 다음에 접으려는 색깔의 두 점이 이미 만나고 있으면, 그 두 점에 대해서는 줄자를 접지 않는다.   예를 들어 길이 10㎝ 인 줄자에 아래 그림과 같이 2㎝ 와 7㎝ 위에에 두 빨간 점이 찍혀 있고, 5㎝ 와 4㎝위치에 파란 점이, 10㎝ 와 3㎝ 위치에 노란 점이 찍혀 있다고 하자. (그림에서 빨간 점은 별표로, 파란 점은 동그라미, 그리고 노란 점은 네모로 표시되어 있다.) 빨간 두 점이 만나도록 줄자를 접으면 줄자의 4.5㎝ 위치에서 접히고 4㎝ 와 5㎝ 눈금이 서로 만나게 된다. 그러면 줄자의 왼쪽 부분의 길이는 4.5㎝ 이고 오른쪽 부분의 길이는 5.5㎝가 되어, 접힌 줄자의 길이는 5.5㎝ 가 된다. 파란 두 점은 이미 만나므로 줄자를 접지 않고, 그런 다음 노란 두 점이 만나도록 접으면 줄자의 길이는 3.5㎝ 가 된다.     줄자의 길이와 각 색깔의 점들이 찍혀있는 위치가 주어질 때, 준성이가 빨간 색, 파란 색, 노란 색의 순서로 두 점이 만나도록 줄자를 접으면 줄자의 길이가 얼마가 되는지를 구하는 프로그램을 작성하시오.   입력 파일의 첫째 줄에 줄자의 길이가 입력된다. 줄자의 길이는 10㎝ 이상, 1,000㎝ 이하이고 단위를 나타내는 ㎝은 입력되지 않는다. 둘째 줄에는 두 빨간 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 셋째 줄에는 두 파란 점의 위치가, 넷째 줄에는 두 노란 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 입력되는 모든 점들의 위치는 서로 다르다. 한 줄에 접은 후의 줄자의 길이를 소수점 이하 한자리까지 출력한다. 소수점 이하 한자리가 0 이면 0 도 출력한다.(예 4.0) 10 2 7 5 4 10 3 3.5 출처 : KOI 전국 2004 초2

문제풀이)

입력 예제와 같이 붉은 점이 2,7 위치에 있고

파랑색 점이 4와 5위치에 있고

노랑색 점이 3과 10위치에 있으며

처음 줄자의 길이는 총 10 인 줄자를 처음에 붉은점이 만나도록 접어야 하므로 (2+7)/2 의 위치인 4.5 위치에서 접게 됩니다.

그렇게 되면 파랑색 점은 4 위치의 점이 5 위치로 가고 5 위치는 그냥 5 위치에 남게 됩니다.(이것을 계산 하는 방법은 각각을 접는 위치와 차이를 구해서 접는 위치 + 차이 를 계산해 주면 오른쪽으로 이동하게 됩니다. 만약 오른쪽에 있는 점이라고 하면 그냥 오른쪽에 있을것이고 왼쪽에 있는 점이라면 접는 방향 오른쪽으로 이동할 것입니다.)

또한 노랑색 점은 3 위치의 점은 6 위치로 이동하고 10위치는 그냥 10위치에 남게 됩니다.

이때 시작점 0 의 위치는 9의 위치로 이동하는데 이것은 마지막 10의 위치보다 안쪽에 있기 때문에 마지막 점은 10의 위치에 그냥 남게 됩니다. 

그리고 4.5 위치에서 접혔기 때문에 시작점은 4.5 위치로 이동하게 됩니다. 따라서 붉은 위치의 지점에서 접은 상태의 길이는 4.5에서 시작해서 10의 위치에서 끝나는 길이 5.5의 줄자의 길이가 됩니다.

그리고 나서 파랑색을 만나게 접으려고 보니 이미 5와 5가 만나 있어서 다시 접을 필요가 없습니다.

따라서 다음 노랑색의 6과 10이 만나도록 접어야 합니다.

노랑색이 만나도록 접기 위해서는 (6+10)/2 = 8 의 위치를 접게 됩니다.

이렇게 접으면 처음 시작점 4.5 는 11.5의 위치로 이동하게 됩니다. 이때 마지막 점인 10 보다 더 큰수가 되기 때문에 이 점이 마지막 점이 됩니다.

그리고 나서 시작점은 접은 위치인 8로 이동하게 되면 이때의 줄자의 길이는 11.5 - 8 = 3.5 의 길이가 남게 됩니다.

이것은 반복문이나 복잡한 알고리즘 없이 그냥 단순하게 몇번만 접는 계산을 하면 될것 같습니다.

다음은 c언어 코드로 구현을 해 보았습니다.

#include <iostream> #include <stdio.h> #include <math.h> using namespace std; int main() {     double r1,r2;//붉은 점 위치     double y1,y2; //노랑색 위치     double b1,b2; //파랑색 위치     double m;     double s=0; //줄자의 시작 위치 초기값은 0     double e;   //줄자의 마지막 위치;     scanf("%lf",&e); //줄자의 마지막 위치를 입력 받자.     scanf("%lf %lf %lf %lf %lf %lf",&r1,&r2,&b1,&b2,&y1,&y2); //점의 위치를 입력 받자     //만약 r1과 r2 가 서로 다른 경우라면 접어서 두 점을 만나게 하자.     if(r1 != r2)     {         m = (r1 + r2)/2; //접을 위치를 결정하자.         //b1과 b2의 위치를 이동하자.         b1 = m + fabs(m-b1); //b1의 위치는 접는 위치 m 에서 m과 b1의 차이를 더하면 그 위치가 나온다.         b2 = m + fabs(m-b2);         //y1과 y2의 위치를 이동하자.         y1 = m + fabs(m-y1); //y1의 위치는 접는 위치 m 에서 m과 y1의 차이를 더하면 그 위치가 나온다.         y2 = m + fabs(m-y2);         //시작점의 위치를 이동하자.         s = m + fabs(m-s);         if(s > e) e = s; //시작점이 마지막 점을 넘어 가는 경우 마지막 점을 바꾼다.         s = m; //접는 위치가 시작점이 된다.     }     //만약 b1과 b2 가 서로 다른 경우라면 접어서 두 점을 만나게 하자.     if(b1 != b2)     {         m = (b1 + b2)/2; //접을 위치를 결정하자.         //y1과 y2의 위치를 이동하자.         y1 = m + fabs(m-y1); //y1의 위치는 접는 위치 m 에서 m과 y1의 차이를 더하면 그 위치가 나온다.         y2 = m + fabs(m-y2);         //시작점의 위치를 이동하자.         s = m + fabs(m-s);         if(s > e) e = s; //시작점이 마지막 점을 넘어 가는 경우 마지막 점을 바꾼다.         s = m; //접는 위치가 시작점이 된다.     }     //만약 y1과 y2 가 서로 다른 경우라면 접어서 두 점을 만나게 하자.     if(y1 != y2)     {         m = (y1 + y2)/2; //접을 위치를 결정하자.         //시작점의 위치를 이동하자.         s = m + fabs(m-s);         if(s > e) e = s; //시작점이 마지막 점을 넘어 가는 경우 마지막 점을 바꾼다.         s = m; //접는 위치가 시작점이 된다.     }     printf("%.1lf",e-s); //마지막 점과 시작점의 차이를 출력 한다.     return 0; }

그냥 순차적으로 접는것을 세번 반복하면 될것 같네요.

정보올림피아드 문제 풀이 리스트 정리