[백준] 11726번 2×n 타일링 해설 및 풀이 (C++)

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

• 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

• 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

[ 문제보러 가기 ]

풀이 도출 과정

• 2 * n 의 타일링은 n값이 하나씩 증가할 때 마다, 발생되는 규칙이 있다.
• DP(다이나믹 프로그래밍)기법의 피보나치 수열로서, f(n) = f(n-1) + f(n-2) 의 규칙을 지닌다.
• n의 값에 따라 배열로 나타내지만, 1번째와 2번째의 수를 지정해야 피보나치의 수열로 n번째 해답을 구할 수 있다.

시간 복잡도

• for문으로 n번 순회 : O(n)

코드

#include <iostream>
#include <string>
using namespace std;
int main() {
  string str;
  string num = "";
  cin >> str;
  bool isMinus = false;
  int result = 0;
  for (int i = 0; i <= str.length(); i++) {
      if (str[i] == '-' || str[i] == '+' || i == str.length()) {
      		// isMinus가 true일 시에, 그 뒤에 나온 정수들을 뺄셈 처리
          if (isMinus) {
              result -= stoi(num);
              num = "";
          }
          // isMinus가 false일 시에(마이너스 기호가 아직 안나왔다는 뜻), 현재 정수까지 덧셈 처리
          else {
              result += stoi(num);
              num = "";
          }
      }
      // '-'와 '+' 기호가 나오기전까지는 string형태의 num을 이어준다.
      else {
          num += str[i];
      }

			  // 한 번 이라도 '-'기호가 나왔다면, isMinus을 true
      if (str[i] == '-') {
          isMinus = true;
      }
  }

  cout << result << '\n';
}