[알고리즘 1단계] [KOI 2016] 타일 장식물

[출처 : Goorm 사이트 - Yun Goon]

문제

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1 인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.

 

 

그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.

 

1, 1, 2, 3, 5, 8, ...

 

지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.

 

타일의 개수 N(1 ≤ N ≤ 80)이 주어졌을 때, N 개의 타일로 구성된 직사각형의 둘레를 구하는 프로그램을 작성하시오.

 

입력 형식

표준 입력으로 다음 정보가 주어진다. 입력은 한 줄로 구성되며 이 줄에는 타일의 개수를 나타내는 정수 N(1 ≤ N ≤ 80)이 주어진다.

 

출력 형식

표준 출력으로 N 개의 타일이 구성하는 타일 장식물 직사각형의 둘레를 출력한다.

 

부분 문제의 제약 조건

• 부분문제 1: 전체 점수 100점 중 21점에 해당하며 N 이 7 이하라고 가정한다.

• 부분문제 2: 전체 점수 100점 중 53점에 해당하며 N 이 40 이하라고 가정한다.

• 부분문제 3: 전체 점수 100점 중 26점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다(이 경우 64비트 정수형인 “long long” 자료형을 써야 할 수 있음).

예시

 

 

---

풀이

key!) 타일 N개가 주어졌을 때 N개의 타일로 구성된 직사각형의 둘레 구하는 프로그램
(1<=N<=80)
1. 입력은 하나 n 

scanf("%d", n);

2. 알고리즘 띵킹
뭔가 딱 봐도 피보나치수열 문제 같다. 나는 똑똑하지 않으니 나열해보면서 규칙을 발견해보자.

N	둘레길이
1	4	=4
2	1*2 + 2*2	= 2 + 4 = 6
3	2*2 + 3*2	= 4 + 6 = 10
4	3*2 + 5*2	= 6 + 10 = 16
5	5*2 + 8*2	= 10 + 16 = 26

결국 피보나치수열.. - 재귀로 풀어볼까?
1) 이전과 이 이전을 더해서 현재 값이 나온다.

f(1) = 4;
f(2) = 6; 
f(n) = f(n-1) + f(n-2) ;

함수로 만들면

int fibo(int n){ 
	if(n==1) return 4; 
	else if(n==2) return 6; 
	else return fibo(n-1)+fibo(n-2); 
} 

이제 코딩해보자.

# 재귀 방식으로 코딩해보기

#include <stdio.h> 
int fibo(int n); 
int main() { 
	long long n; 
	scanf("%d", &n); 
	printf("%d", fibo(n)); 

	return 0; 
} 
int fibo(int n){ 
	if(n==1) return 4; 
	else if(n==2) return 6; 
	else return fibo(n-1) + fibo(n-2); 
} 

# 결과

 

잘 나가다가 17번 부터 FAIL..

 

실패이유)
1. 값이 커질수록 재귀의 깊이가 깊어졌을 때, stack overflow가 발생하면서 프로그램이 비정상적으로 종료된다.
2. 함수의 stack frame을 구성하고 해제하는 과정에서 반복문보다 많은 overhead가 들기 때문에 속도도 훨씬 느려진다. => 결국 timeout fail이 발생

 

**여기서 다시 보는 메모리 구조!

함수를 호출하면 함수의 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치가 stack에 함께 저장된다.

 

 

 

 

## 그럼 반복문으로 코딩해보자

#include <stdio.h>
int fibo(int n);
int main() {
	long long n, output;
	long long result1=4;
	long long result2=6;
    
	scanf("%lld", &n);
	if(n==1)	output = 4;
	else if(n==2)	output = 6;
	else{

		for(int i=0; i<n-2; i++){
			output = result1 + result2;
			result1 = result2;
			result2 = output;
		}
	}
	printf("%lld", output);
	return 0;
}

# 결과

 

 

입력이 많아지는 17번 이후로도 실행이 잘 된다!

# 재귀(Recursion) vs 반복문(Iteration)

한 블로거 님께서 잘 정리해주셨다! 

velog.io/@ljinsk3/반복문Iteration-vs-재귀Recursion

반복문(Iteration) vs 재귀(Recursion)

재귀는 풀이를 더 명확하게 만들어 준다. 그러나 재귀를 쓴다고 반드시 성능이 더 나아지지는 않는다.

 

"프로그램에 반복문을 사용하면 프로그램의 성능을 향상할 수 있지만, 재귀를 사용하면 프로그래머의 능력을 향상시킬 수 있습니다. 상황에 따라 적절한 방법을 골라 사용하세요." -Leigh Caldwell (stackoverflow.com)

 

 

 

ps. 이게 초등학교 2학년 대상 문제였다고?????......

 

---

* 개인적인 학습 목적으로 작성한 글이기에 내용에 잘못된 정보가 있을 수 있습니다.

* 문제 출처 - level.goorm.io/exam/48135/타일-장식물/quiz/1