[codesignal][python] 3. shapeArea

codesignal.com

Coding Tests and Assessments for Technical Hiring | CodeSignal

level : easy

Question:

Below we will define an n-interesting polygon. Your task is to find the area of a polygon for a given n.

A 1-interesting polygon is just a square with a side of length 1. An n-interesting polygon is obtained by taking the n - 1-interesting polygon and appending 1-interesting polygons to its rim, side by side. You can see the 1-, 2-, 3- and 4-interesting polygons in the picture below.

 

문제는 아래 그림처럼 n이 주어졌을 때 해당하는 모양의 면적(파란색 부분 면적)을 반환하는 알고리즘을 작성하는 문제이다.

 

Example: 

• For n = 2, the output should be shapeArea(n) = 5;
• For n = 3, the output should be shapeArea(n) = 13.

 

My answer:

<처음 문제 풀 때>

def shapeArea(n):
    if n==1:
        return 1
    
    else:
        return shapeArea(n-1)+(n+2*(n-1)+(n-2))

n=1일 경우 1을 반환하고 

n>=2부터는 n-1일때의 면적에 테두리 각 변의 면적을 더하는 형태로 재귀적으로 문제를 접근했다.

예를 들어, n=3일때는 n=2일때의 면적에 겉 테두리 왼쪽상단 (3) + 왼쪽하단(2)+오른쪽하단(2)+오른쪽상단(1) 형태로 겹치는걸 제외하고 각 변을 더해주는 방식으로 문제를 풀었다. 

결과적으로 테스트셋 10개중 6개만 통과하고 문제를 틀렸는데 아마 "재귀호출" 이 n이 커지면서 time out에 걸렸거나 stack limit에 걸렸다고 생각한다.

 

그래서 결국 직접 점화식 풀어서 해결  : (n**2+(n-1)**2)

<수정후>

def shapeArea(n):
	(n**2+(n-1)**2)