이번 문제는 정말 어려웠다...! 한참을 고민해도 답을 찾지 못해서, 푸신 분들의 블로그를 찾다가 재귀를 활용해 굉장히 간단하게 구현하신데다 설명도 이해하기 쉽게 써주신 분의 블로그를 참조해 문제를 풀 수 있었다!(https://mgyo.tistory.com/183)
풀이
별을 당장 찍는 방식이 아니라, 미리 0과 1로 구성된 이차원 배열을 만들고 재귀 함수를 이용해 별이 찍힐 위치만 1로 표시한 뒤, 나중에 해당 배열을 출력하며 1은 '*'로, 0은 공백으로 출력하는 방법이었다.
재귀 방식도 간단했는데, map의 [0][3:6], map의 [0][6:9]..이렇게 열(x값)에 3씩 더한 값이 map의 [0][:3] 과 동일하고, map[3][0:3], map[6][0:3] 이렇게 행(y값)에 3씩 더한 값도 map[0][:3]과 동일하기 때문에 N==3일 때의 패턴만 알면 규칙성을 이용해 나머지 패턴을 모두 구할 수 있는 원리였다.
# 2447. 별 찍기 - 10 2792ms https://mgyo.tistory.com/183 참고
def recursion(N):
global map
if N == 3:
map[0][:3] = map[2][:3] = [1, 1, 1]
map[1][:3] = [1, 0, 1]
return
else:
a = N // 3
recursion(N // 3)
for i in range(3):
for j in range(3):
if i == 1 and j == 1:
continue
for k in range(a):
map[a * i + k][a * j: a * (j + 1)] = map[k][:a]
return
N = int(input())
map = [[0 for _ in range(N)] for z in range(N)]
recursion(N)
for y in range(N):
for x in range(N):
if map[y][x] == 1:
print('*', end='')
else:
print(' ', end='')
print()
굉장히 어려운 문제였지만, 규칙성을 찾으려고 노력한다면 그렇게 어렵지 않을 수도 있다는 것을 느낀 문제!
(하지만 그 규칙성을 찾아내는 게 원래 제일 어려운 일이지..ㅠ)
'개발 공부 > 알고리즘 문제풀이' 카테고리의 다른 글
[삼성SW테스트 준비] 순열과 조합 연습 문제-1 (백준 15649, 15654, 15655, 15657, 15663, 15664, 15665, 15666) (0) | 2022.08.10 |
---|---|
[백준]11729. 하노이 탑 이동 순서 (0) | 2022.08.02 |
[백준] 17478. 재귀함수가 뭔가요? (0) | 2022.08.02 |
[백준] 10872 팩토리얼, 10870 피보나치 수 5 (0) | 2022.08.02 |
[백준] 4948. 베르트랑 공준 (0) | 2022.07.31 |