펭로그

문제 링크 : https://boj.kr/1149 어떤 집을 R, G, B 중 하나로 색칠할 때 인접한 이웃 끼리는 서로 색이 겹치면 안된다. 한 집을 R로 선택하게 되면 그 다음에 올 수 있는 이웃의 값은 G, B 중에 하나만 올 수 있게 된다.그 중에 G를 선택했다면 그 다음 값은 R, B 중에 선택해야 한다.R, G, B의 3가지 값 중에서 하나를 선택하면 그 값을 제외한 2가지를 선택할 수 있다.2가지 선택값 중에서 하나를 선택하면 그 뒤에는 또 2가지를 선택할 수 있는 경우의 수가 주어진다.이 과정을 반복하면 3*2*2*2* .....가지의 경우의 수가 나오며 일반항으로 고쳐보면 3*2^(N-1)가지의 경우를 계산해야 함을 알 수 있다.이를 빅-오 표기법으로 바꿔보면 O(2^N)임을 알 수 있다..