삼각화단 만들기

1. 문제

<출처 : 한국정보올림피아드 (2002 전국본선 초등부) >

 

2. 문제 분석

이 문제의 핵심은 "비선형 탐색이 반드시 답이 아니다." 라는 것을 보여주는 문제이다.

결론부터 말하면, 이 문제는 재귀를 쓰는 방식보다 for문을 3번 돌려서 구하는 것이 빠르다.

우리는 2가지 방식 전부를 만들어 볼 것 이다.

 

그리고, 이 문제를 해결하기 전에 한 가지 약속을 하자.

아래와 같은 가정을 하는 이유는 밑에 나온다.

삼각형의 각 변의 길이를 A,B,C라고 두면,

C를 가장 긴 변, B는 C다음으로 긴 변, A를 가장 작은 변이라고 가정하자.

( A <= B <= C )

위의 조건에서 등호가 붙어도 되는 이유는 세 변의 길이가 같으면 정삼각형이기 때문이다.

그리고, 탐색 시, 각 변의 길이는 모두 1m에서 출발 한다.

각 변의 길이를 모두 1로 세팅한 상태에서 탐색을 하는 것이 쉽게 접근할 수 있다.

그리고, 다음과 같은 조건도 기억해두자.

 

1. 화단의 둘레의 길이 = A + B + C

2. A + B > C  

 

그리고, 다음과 같이 2개의 삼각형이 있다고 가정해보자.

위의 화단은 서로 다른 화단이라고 말할 수 있을까?

변의 순서는 다르지만, 삼각형의 각 변의 길이는 같다.

즉, 이 경우는 두 화단 모두 같은 경우이다.

즉, 이와 같은 가정을 한 이유가 바로 서로 다른 화단이 생길 경우에

값을 하나 증가 시키는 방향으로 프로그램을 만들 것인데,

위와 같이 서로 중복이 되는 삼각형은 제외를 시켜야 한다.

위의 중복을 피하기 위해서는 배열을 하나 선언해서 기록을 통해,

이와 같은 중복을 피할 수 있다.

위와 같이 삼각형의 구성 조건이 만족 될 때, 세 변의 길이를 기록한다.

 

아래의 함수는 탐색을 진행할 함수이다.

기본적인 탐색은 재귀함수의 호출이므로 재귀 함수의 호출 스택에 대해 알아보자.

위의 함수와 같이 보도록 하자. 함수의 첫 탐색의 시작은 세 변의 길이가 모두 1m부터 이다.

위 그림에서 배열 공간의 왼쪽부터 삼각형의 세 변의 길이이며 나머지는 화단의 길이이다.

즉, 탐색 시에 각 변의 길이를 하나씩 증가시키면서 세 변의 길이의 합이 화단의 길이가 되면 탐색을 멈추는 것이다.

그러면 위의 그림과 같이 화단은 총 9개가 만들어지는 것을 알 수 있는데, 이는 틀리다.

그 이유는 삼각형의 세 변의 길이가 3,1,1은 삼각형이 만들어지지 않는다.

그 이유는 두 변의 길이의 합은 3보다 커야 한다. 그리고 세 변의 길이가 2,2,1과 1,2,2는 서로 같은 삼각형이므로 

중복을 배제해야 한다.

즉, 화단은 하나만 존재한다.

삼각형의 성립 조건과 변의 길이가 중복이 되는 삼각형을 제거해야 하기 위해서 다음과 같은 가정이 필요하다.

C를 가장 긴 변, B는 C다음으로 긴 변, A를 가장 작은 변이라고 가정한다. ( A <= B <= C )

위의 가정에 따라 삼각형의 성립 조건은, A + B > C 가 만족이 되야 한다.

 

그리고, 한 가지 더 중복을 제거해야 한다. 그 중복은 입력 길이가 6이상일 때부터 나타난다.

아래는 재귀 함수의 호출 스택의 일부분만 나타낸 것이다. (호출하는 부분이 너무 많다.)

궁금하면 직접 그려보도록 하자.

위 그림에서 보다시피 1과 2는 서로 세 변의 길이가 1,2,3이다. 그런데 중복 호출됨을 알 수 있다.

이 중복을 막기 위해서 메모이제이션 기법이 필요하다.

이는 삼각형이 성립할 때, 그 세 변의 길이를 기록을 함으로써 중복을 막을 수 있다.

3차원 배열을 이용해서 기록을 하도록 한다.

 

3. 구현

 

실행결과

4. 소스 파일

main.c

0.00MB