2447 별찍기 10

예제로 주어진 별찍기를 보고 패턴을 예측해서 주어진 입력에 맞는 크기의 별을 찍는 문제이다.

별찍기라해서 방심해선안된다. 생각보다 까다롭기 때문이다. 예제를 살펴보자.

쳐다만봐도 다른 문제를 풀고싶지 않은가?

사실 본인도 한번 포기했다가 다시 도전한 문제이다.

이 문제는 패턴을 잘 생각해야하는데, 내가 찾아낸 패턴은 다음과 같다.

잘 보면 중간마다 별이 끊어져 있는것을 알 수 있는데, 첫 줄을 0이라고 놓고 별이 새롭게 끊켜지는 줄 번호를 살펴보자.

1 <= L < 2

3 <= L < 6

9 <= L < 18

규칙이 보이는가? L은 1부터 시작해서 3배로 증가하는 위치마다 별이 끊키게 된다.

이 시작 라인을 start, 경계 라인을 end라고 하면

start = 1, start = start * 3

end = start * 2

과 같은 관계가 된다.

여기서 또 알 수 있는건, 각 줄의 끊어지는 위치도 start와 관계가 있다는 것이다.

라인 1을 보자. 3칸마다 1칸씩 끊어져 있는것을 볼 수 있을 것이다.

라인 3도 보자. 9칸마다 3칸씩 끊어져 있는것을 볼 수 있다.


그렇다. 한번에 끊어지는 간격도 start * 3칸 마다 중앙의 start 칸씩 끊어져 있게 된다.
그런데 라인 4를 보면  3칸에 1칸씩도 끊어져 있다. 이것은 과거에 만들어져 있던 라인을 가지고 끊기 때문이다. 과거에 참고하는 라인또한 현재라인 - start 이다.

마지막으로 현재 라인이 end로 설정한 라인과 같다면, 과거에 만들어준 별을 그대로 다시 출력해야 한다. 그것도 0 <= L < start 까지이다.

설명한대로 구현해준다면 답을 얻을 수 있다.

소스