[BOJ 10993] 별 찍기 - 18 (OCaml)

구현 문제

근데 이제 Ocaml을 곁들인

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

 

---

문제 풀이

패턴이 일반적이지 않으므로 재귀를 떠올릴 수 있어야 합니다.

또한 별을 찍을 때는 무조건 2차원 배열에 특정한 패턴으로 찍는다는 생각으로 푸셔야 합니다.

 

---

우선 2차원 배열의 크기부터 계산해 보겠습니다.

 

n	h	w
1	1	1
2	3	5
3	7	13
4	15	29

 

전체 크기를 측정하면 위와 같습니다.

규칙을 찾아 일반항을 도출하면 $h = 2^n -1, w = 2h - 1$입니다.

 

---

n = 4

 

위는 n = 4인 경우입니다. 이제부터 빨간 부분은 밑변, 파란 부분은 첨점으로 표현하겠습니다.

또한 재귀를 사용하며, 다음 단계로 넘어갈수록(재귀가 깊어질수록) n이 작아지는 재귀로 문제를 풀이하겠습니다.

w 좌표는 왼쪽이 작고, h 좌표는 위쪽이 작습니다.

 

특징을 관찰한 결과는 아래와 같습니다.

 

• 현재 단계의 n이 짝수일 때, 밑변이 위쪽에 있는 역삼각형 모양이 됨을 알 수 있습니다. n이 홀수라면 반대입니다.
• 현재 단계에서의 h 좌표가 [h1, h2] 범위를 갖는다면 다음 단계의 밑변은 (h1+h2)/2입니다.
• 현재 단계의 n이 짝수일 때, 밑변의 h 좌표가 h1이라면 다음 단계의 첨점은 h1+1입니다. n이 홀수라면 h1-1입니다.
• 위에서 계산한 2차원 배열의 w크기의 일반항을 사용하여 별을 찍으면 됩니다. 중앙으로부터 퍼져나가는 방식입니다.
• 현재 단계의 n이 짝수일 때, 첨점으로부터 위로 한칸씩 올라가면서 좌우로 한칸씩 퍼져나가도록 점을 찍으면 빗변도 채울 수 있습니다. n이 홀수라면 아래로 한칸씩 내려가면 됩니다.
• n = 1인 경우, 첨점과 밑변의 좌표가 정확하게 일치합니다. 이 경우에 도달하면 해당 좌표에 별을 찍고 재귀를 종료합니다.

위의 특징을 활용하고, 파라미터로 h범위(h1, h2), w범위(h1, h2), 재귀의 깊이(n)를 가져가면서 재귀 함수를 작성하시면 문제를 해결할 수 있을 겁니다.

 

---

소스 코드 / Ocaml

 

module F = Format

let rec print_1d lst_1d x dx = 
  match lst_1d with
  | [] -> ()
  | h :: t -> (
    if x = dx then F.printf "%c\n" h
    else (
      F.printf "%c" h;
      print_1d t x (dx + 1)
    )
  )

let rec print_2d_upper lst_2d x =
  match lst_2d with
  | [] -> ()
  | h :: t -> (
    print_1d h x 0;
    print_2d_upper t (x + 1)
  )

let rec print_2d_lower lst_2d x =
  match lst_2d with
  | [] -> ()
  | h :: t -> (
    print_1d h x 0;
    print_2d_lower t (x - 1)
  )

let rec get_1d lst_1d x dx =
  match lst_1d with
  | [] -> 0
  | h :: t -> (
    if dx = x then h
    else get_1d t x (dx + 1)
  )

let rec get_2d lst_2d y x dy =
  match lst_2d with 
  | [] -> 0
  | h :: t -> (
    if dy = y then get_1d h x 0
    else get_2d t y x (dy + 1)
  )

let rec set_oneline_1d lst_1d l r dx =
  match lst_1d with
  | [] -> []
  | h :: t -> (
    if l > dx then h :: set_oneline_1d t l r (dx + 1)
    else (
      if dx > r then h :: t
      else '*' :: set_oneline_1d t l r (dx + 1)
    )
  )

let rec set_oneline_2d lst_2d l r y dy =
  match lst_2d with
  | [] -> []
  | h :: t -> (
    if dy = y then set_oneline_1d h l r 0 :: t
    else h :: set_oneline_2d t l r y (dy + 1)
  )

let rec set_1d lst_1d x0 x1 dx =
  match lst_1d with
  | [] -> []
  | h :: t -> (
    if dx = x0 then '*' :: set_1d t x0 x1 (dx + 1)
    else (
      if dx = x1 then '*' :: set_1d t x0 x1 (dx + 1)
      else h :: set_1d t x0 x1 (dx + 1)
    )
  )

let rec make_1d x =
  if x = 0 then []
  else ' ' :: make_1d (x - 1)

let rec make_2d y x = 
  if y = 0 then []
  else (make_1d x) :: make_2d (y - 1) x

let rec draw_upper lst_2d x0 x1 y0 y1 dy =
  match lst_2d with
  | [] -> []
  | h :: t -> (
    if y0 > dy then h :: draw_upper t x0 x1 y0 y1 (dy + 1)
    else (
      if dy > y1 then h :: t
      else set_1d h x0 x1 0 :: draw_upper t (x0 - 1) (x1 + 1) y0 y1 (dy + 1)
    )
  )

let rec draw_lower lst_2d x0 x1 y0 y1 dy =
  match lst_2d with
  | [] -> []
  | h :: t -> (
    if y0 > dy then h :: draw_lower t x0 x1 y0 y1 (dy + 1)
    else (
      if dy > y1 then h :: t
      else set_1d h x0 x1 0 :: draw_lower t (x0 + 1) (x1 - 1) y0 y1 (dy + 1)
    )
  )

let rec drawing lst_2d x0 x1 y0 y1 depth =
  if depth = 0 then lst_2d
  else (
    let half_d = depth / 2 in
    if half_d * 2 = depth then (
      let lst_2d_1 = set_oneline_2d lst_2d x0 x1 y0 0 in
      let lst_2d_2 = draw_lower lst_2d_1 x0 x1 y0 y1 0 in
      let dx = (x1 - x0) / 4 in
      drawing lst_2d_2 (x0 + dx + 1) (x1 - dx - 1) (y0 + 1) ((y0 + y1) / 2) (depth - 1)
    ) else (
      let lst_2d_1 = set_oneline_2d lst_2d x0 x1 y1 0 in
      let lst_2d_2 = draw_upper lst_2d_1 ((x0 + x1) / 2) ((x0 + x1) / 2) y0 y1 0 in
      let dx = (x1 - x0) / 4 in
      drawing lst_2d_2 (x0 + dx + 1) (x1 - dx - 1) ((y0 + y1) / 2) (y1 - 1) (depth - 1)
    )
  )

let n = int_of_string (read_line())
let w = 4 * (1 lsl (n - 1)) - 3
let h = 1 lsl n - 1
let stars = make_2d h w
let ans = drawing stars 0 (w - 1) 0 (h - 1) n

let _ =
  let half = n / 2 in
  if half * 2 = n then print_2d_lower ans (w - 1)
  else print_2d_upper ans ((w - 1) / 2)