[BOJ/백준 - 2447] 별 찍기 - 10

문제 출처 : https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

---

---

정답비율이 오늘 기준으로 53.247%인데... 어려운데?

 

일단 내가 문제를 풀면서 사용한 가장 큰 틀은 '우측하단을 잡고 땡긴다' 였다

(표현이 뭐 정확하진 않지만 나는 이런생각으로 잡았음)

 

그림으로 보자면 밑에와 같은 형식일 것이다

 

N이 3인 경우

N이 9인 경우

 

(이하 설명은 N이 9인 상태(밑의 그림)를 기준으로 설명하겠음)

자 그럼 틀을 잡았으니까 어떻게 진행하게 됬냐면

 

처음 가지고 있는 상태 ( 위에 그림의 왼쪽 상태 ) 부터

1. 특정 지점의 좌표들을 순회하면서

2. 처음 가지고 있는 상태를 복사한다

이 두가지다 

 

내가 특정 지점의 좌표를 선택한 기준은 처음 가지고 있는 상태만큼의 크기로 9등분을 해서 각 왼쪽상단의 좌표이다

그림으로 보면 맨 왼쪽이 3*3이므로 9*9 배열을 각각 나눠 9등분하여서 맨 왼쪽상단의 좌표를 선택한다

내가 순회해야 하는 좌표를 출력하면

위와 같이 될것이다 그리고 반복문 상 

(0, 0)의 위치와 (3, 3)의 위치도 확인하지만 

(0, 0) 왼쪽상단의 좌표는 -> 복사할 필요가 없음

(3, 3) 중앙의 좌표는 -> 복사하면 안됨

 

특정 좌표를 얻어낸다면 각 위치에서 맨 왼쪽 3*3의 값을을 복사해서 채워 넣는다

 

N이 9인경우를 구했다고 하고 N이 27이라고 생각해보자 (그림은 안붙이겠음, 너무 큼)

27일 경우 내가 순회할 좌표를 알아보자 

위의 좌표를 순회하게 될것이고 각 좌표에서부터 앞서 구한 

0,0부터 9*9 크기의 상태값을 복사해 넣어준다

 

의식하고 사용하진 않았는데 메모이제이션을 사용해 풀게 되었다

예전엔 못풀고 넘어갔던거같은데... 뽀록이 터졋다