백준 - 2448번(재귀)

https://www.acmicpc.net/problem/2448

2448번: 별 찍기 - 11

 

import sys

def triangle(s,t,l,k): #s = 재귀 호출 횟수, t = 삼각형 리스트, l = 삼각형 밑변의 길이, k = n 
  c = 3 * (2 ** s) # 삼각형 한변의 길이

  if c == k: #한변의 길이가 n과 같으면 출력후 종료
    for i in t:
      print(i.center(k*2)) #center 함수를 통해서 위치 조정
    return 1

  else: #아니라면 t를 규칙에 맞게 복제해서 추가 
    for i in range(c):
      t.append(t[i] + " " * (int(l) - (i * 2)) + t[i])
    triangle(s+1,t, len(t[-1]), k) # 재귀 호출


n = int(sys.stdin.readline()) #n입력

t = ['*',"* *","*****"] #기본 삼각형

triangle(0,t,5,n) #함수 실행

 

기본적인 원리는 다음과 같다.

n = 3 일 때 밑변의 길이 5인 삼각형(a라고 가정한다.)을 가장 작은 하나의 단위로 생각한다.

앞으로 단위 삼각형으로 부르겠다.

n = 6일때는 a가 삼각형 밑에 2개가 붙어 있는 모습이다. 다음 삼각형에서는 방금 붙인 삼각형이 단위 삼각형이 된다.

이를 반복하면 되는데 단위 삼각형을 만들 때 밑에 삼각형 두 개를 붙일 때 두 개의 삼각형의 띄어쓰기 간격을 생각해 줘야 한다.

그 규칙은 아래와 같다.

    for i in range(c):
      t.append(t[i] + " " * (int(l) - (i * 2)) + t[i])

 

기존 삼각형에 추가적으로 밑에 두개를 붙여주면 더 큰 삼각형 하나가 된다.

이것이 다음 삼각형의 하나의 단위가 되는 것이다.

따라서 새롭게 만들어진 t를 넣어서 재귀 호출을 한다.

문제에서 규칙을 파악해야 하는데 이등변 삼각형을 만드는 문제다.

밑변을 제외한 양변의 길이는 같고 해당 길이가 n가 동일하면 우리가 구하고자 하는 삼각형이 완성이 된 것이다.

그리고 띄어쓰기 규칙은  이전 단위 삼각형의 밑변의 길이를 띄어쓰기 값으로 가지면서 한 줄씩 늘어날 때마다 2의 배수로 줄어든다.

우리가 처음에 만든 최초의 단위 삼각형이 1,3,5 꼴로 증가하기 때문에 자명하다.

 

해당 양옆 변의 길이가 k가 되면 누적된 삼각형들을 출력해주면 되는데 이때 가장 마지막에 만들어진 출력하고자 하는 삼각형의 가장 밑변을 기준으로 중앙 정렬을 해야 우리가 찾는 모양이 나온다.

이때 center 함수를 사용해주면 된다. 가장 밑변의 길이는 항상 n*2 이므로 해당 기준에 맞춰서 출력시켜주면 된다.