알고리즘/백준(acmicpc.net) 문제풀이
-
2193번 : 이친수알고리즘/백준(acmicpc.net) 문제풀이 2018. 5. 31. 15:16
이차원 dp로 구성한다.dp[i][2]로 구성하는데 dp[i][0]는 i자리 이친수 중 가장 뒷자리가 0인 수를, dp[i][1]는 i자리 이친수 중 가장 뒷자리가 1인 수를 의미한다. dp[i-1][0] 뒤에 0이 올 수 있고 dp[i-1][1] 뒤에도 0이 올 수 있다.dp[i-1][1] 뒤에는 0만 올 수 있다. 여기서 N이 90까지이므로 long long int로 구성한다. #include long long int dp[91][2], N; //마지막자리가 0으로 끝나는지, 1로 끝나는지 => 개수 int main() {dp[1][0] = 0;dp[1][1] = 1;dp[2][0] = 1;dp[2][1] = 0;scanf("%d", &N);for (int i = 3; i
-
2579번 : 계단 오르기알고리즘/백준(acmicpc.net) 문제풀이 2018. 5. 30. 20:03
2006년 초등부 지역본선 4번 문제입니다. 조건을 다시 되짚어보면한번에 최대 두 칸 위까지 올라갈 수 있다.연달아 3칸을 밟으면 안된다.도착 지점은 무조건 밟아야 한다. dp는 i번째 계단을 밟을때와 밟지 않을 때 각각의 최대 점수를 dp로 쌓아주시면 됩니다.즉 dp[3][1]은 3번째 칸을 밟았을 때 최대 점수이고, dp[3][0]은 3번째 칸을 밟지 않았을 때(건너 뛰었을 때)의 최대 점수입니다. 0. dp[0][0], dp[0][1], dp[1][0]은 0으로 초기화, dp[1][1]은 1번 칸 값으로 초기화.1. 해당 칸을 밟지 않았을 때는 그 전칸은 무조건 밟았다는 소리가 됩니다. 따라서 dp[i][0]은 dp[i-1][1]이 됩니다.2. 해당 칸을 밟았을 때는 dp[i-1][0]과 dp[i-..
-
1003번 : 피보나치 함수알고리즘/백준(acmicpc.net) 문제풀이 2018. 5. 30. 19:25
기본적인 DP입니다. 0에서 0의 개수는 1개, 1의 개수는 0개1에서 0의 개수는 0개, 1의 개수는 1개2는 0과 1로 쪼개지면서 0의 개수는 1개, 1의 개수는 1개3은 1과 2로 쪼개지면서 0의 개수는 1개, 1의 개수는 2개4는 2와 3으로 쪼개지면서 0의 개수는 2개, 1의 개수는 3개 즉, 4에서의 0의 개수는 2에서의 0의 개수와 3에서의 0의 개수를 더하면 되겠죠. 1도 마찬가지구요 #include int dp[100][2]; //[0] : 0, [1] : 1 int T; int f_0(int n) {if (dp[n][0]!=-1) return dp[n][0];else return dp[n][0]=f_0(n - 1) + f_0(n - 2);} int f_1(int n) {if (dp[n]..