룰루랄라 코딩기록장

11762번 2xn타일링 문제 풀이 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력 2 9출력 2 55코드 #include #include #include using namespace std; int d[1001]; int n; int top_down(int n) { if (n == 0) return 1; if (n == 1) return 1; if (d[n] > 0) return d[n] %= 10007; d[n] = top_down(n - 1) + top_down(n - 2);..

Top-down int top_down(int n) { if (n == 1) return 0; if (d[n] > 0) return d[n]; d[n] = top_down(n - 1) + 1; if (n % 2 == 0) { int temp = top_down(n / 2) + 1; if (d[n] > temp) d[n] = temp; } if (n % 3 == 0) { int temp = top_down(n / 3) + 1; if (d[n] > temp) d[n] = temp; } return d[n]; } 큰 문제를 작은 문제로 나누어서 풀이한 후 큰 문제의 정답을 알아내는 방법이다. 즉 n이 6인경우를 구할 때 d[6]을 알기 위해서는 작은 결과값인 d[5], d[4], d[2]의 결과 값 중 최소값..

3055번 탈출 문제 풀이 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으..