실력키우기 줄자접기(C++)

1112 : 줄자접기

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 429 회    시도횟수: 1209 회   

준성이는 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)

[Copy] 10 2 7 5 4 10 3

[Copy] 3.5

출처 : KOI 전국 2004 초2

/**************************************************************
    Problem: 1112
    User: a132034
    Language: C++
    Result: Success
    Time:0 ms
    Memory:1092 kb
****************************************************************/
 
 
#include    <cstdio>
#include    <algorithm>
#pragma warning(disable:4996)
 
int dot[4][3];
int main()
{
    double len;
    scanf("%lf", &len);
    for (int i = 1; i <= 3; ++i)
        scanf("%d%d", &dot[i][1], &dot[i][2]);
 
    for (int i = 1; i <= 3; ++i)
    {
        if (dot[i][1] != dot[i][2])
        {
            double loc = (double)(dot[i][1] + dot[i][2]) / 2.0;
            if (loc < len - loc)
            {
                for (int j = i + 1; j <= 3; ++j)
                {
                    for (int k = 1; k <= 2; ++k)
                    {
                        if (dot[j][k] > loc)
                            dot[j][k] = len - dot[j][k];
                        else//같은 경우도 포함
                            dot[j][k] += (len - loc - loc);
                    }
                }
                len -= loc;
            }
            else
            {
                for (int j = i + 1; j <= 3; ++j)
                {
                    for (int k = 1; k <= 2; ++k)
                    {
                        if (dot[j][k] > loc)
                            dot[j][k] = loc - (dot[j][k] - loc);
                    }
                }
                len = loc;
            }
        }
    }
    printf("%0.1lf", len);
    return 0;
}

실제로 줄자모양으로 종이를 만들면 가장 좋을 것 같다. 아니어도 충분히 수식을 이끌어 낼 수 있긴 하다. 

접을 떄 마다 남은 점들은 위치가 바뀔 것이다. 

두 가지 경우의 수로 나누어 볼 수 있다. 

1. 접는 점 기준으로 앞이 긴 경우

2. 접는 점 기준으로 뒤가 긴 경우

1의 경우 접는 점을 기준으로 앞의 색의 위치는 기존과 동일할 것이고, 뒤의 색의 위치는 변화가 있을 것이다. 

 뒤의 위치 변화는 42라인의 else에서 구현하였다. 

2의 경우에는 앞의 색, 뒤의 색 모두 변화가 있을 것이다. 

 28라인의 if문에서 앞, 뒤의 위치 변화를 구현하였다. 

식은 실제로 종이를 만들어 보거나, 생각해본다면 어렵지 않게 나올 것이기 떄문에 설명은 생략..