이번 연습문제는 파스칼의 삼각형을 출력하는 문제이다.
출처 : https://www.hackerrank.com/challenges/pascals-triangle/problem
파스칼의 삼각형을 출력한다. 숫자의 정렬은 무시하고 입력받는 정수 n행까지의 숫자 리스트를 공백으로 띄워서 출력한다.
접근
출력은 다음과 같은 모양이다.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
....
이 중에 4행과 5행을 보자.
1 3 3 1
+ 1 3 3 1
-------------
1 4 6 4 1
특정한 행을 어슷하게 배치해서 각 위치의 숫자를 더하면 그 다음 행이 된다. 그렇다면 [1, 3, 3, 1, 0]과 [0, 1, 3, 3, 1] 두 리스트에 대해서 같은 위치에 있는 원소끼리 더해서 하나의 리스트를 만들면 된다.
이 동작은 zipWith라는 기본함수가 멋지게 표현해줄 수 있다. (http://hackage.haskell.org/package/base-4.10.0.0/docs/Prelude.html#v:zipWith)
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
따라서 파스칼의 삼각형의 n 번째 행의 숫자 리스트를 만드는 함수를 생각해보자.
pasT :: Int -> [Int]
pasT 1 = [1]
pasT n =
let ns = pasT (n-1)
in zipWith (+) (0:ns) (ns++[0])
이를 1..n의 범위에 대해서 구하고 합쳐서 출력하면 끝.
import Control.Monad
main :: IO ()
main = do
n <- readLn :: IO Int
forM_ [1..n] $ \a ->
putStrLn . unwords . map show $ pasT a