목록DP알고리즘 (1)

DNF LOVE

[JAVA, C++] 백준 11726번 2xn 타일링 문제 - DP 알고리즘

DP알고리즘의 또 다른 문제 2xn타일 구하기 문제이다. 이 문제도 어제 풀었던 1, 2, 3 더하기와 똑같은 원리로 이루어져 있다. 우선, 타일은 2x1 과 1x2 이 두가지가 주어진다. 그러다면 우리가 바로 알 수 있는 경우의 수는 1일떄와 2일때이다. tile[1] 일때, 2x1 하나밖에 쓰이지 못하니 경우의 수는 1이다. 또, tile[2] 일때, 2x1 타일을 두개 겹친 것과 1x2 타일을 가로로 두 개 겹친 것해서 경우의 수는 2가지가 나온다. 그렇다면 3일때는 어떨까? 2x1타일을 앞에 세울 때, 2가지 경우와 1x2타일을 두개로 겹쳐서 2x2로 만들때 1가지 경우의 수를 더하면 3가지의 경우의 가지가 나온다. 그렇다. 2x1타일을 맨 앞에 세웠을 때의 경우의 수와 1x2타일을 가로로 겹쳐 ..
Algorithm/문제 풀이 2019. 7. 16. 23:19
이전 Prev 1 Next 다음