본문 바로가기

알고리즘/BOJ

알고리즘/BOJ 2020. 3. 14. [C++] 백준 9465번 - 스티커 0. 문제 1. 아이디어 1) 열을 기준으로 하나씩 늘려나가며 각 경우의 수에 대한 최댓값을 기록해둔다. 2) N번째 열에 선택될 수 있는 점수는, 1. N-1번째 열에서 스티커가 떼어지지 않았을 때, 2. N-1번째 열에서 위 스티커가 떼어졌을 때, 3. N-1번째 열에서 아래 스티커가 떼어졌을 때. 총 3가지의 경우로 나누어서 생각할 수 있다. 3) 그렇게 시작해서 1번째 열까지 범위를 넓혀오면 정답을 찾을 수 있다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include const int MAX = 100000;..
알고리즘/BOJ 2020. 3. 14. [C++] 백준 2193번 - 이친수 0. 문제 1. 아이디어 1) 1. 0으로 시작할 수 없다 와 2. 1은 연속해서 나오지 못한다 를 고려해서 문제를 푼다. 2) 즉, N=1일 때 나올 수 있는 건 '1' 하나 뿐이고 N 레벨에서 1이 나오려면 N-1 레벨에선 반드시 0이어야만 한다. (0은 상관 없음) 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include int main() { int N; std::cin >> N; long long dp[91][2] = { 0, }; dp[1][1] = 1; for (int i = 2; i
알고리즘/BOJ 2020. 3. 14. [C++] 백준 11057번 - 오르막 수 0. 문제 1. 아이디어 1) 10844번과 동일한 아이디어. (여기선 자리수 이하의 모든 수가 가능하다는 점이 다름) 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #define MOD 10007 int main() { int N, sum = 0; std::cin >> N; int dp[1001][10] = { 0, }; for (int i = 0; i
알고리즘/BOJ 2020. 3. 14. [C++] 백준 10844번 - 쉬운 계단 수 0. 문제 1. 아이디어 N=1 → 1, 2, 3, 4, 5, 6, 7, 8, 9 N=2 → 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 1) 이처럼 수의 길이가 N일 때 계단수는, 길이가 N-1인 계단수에 일의 자리 +-1을 붙여주면 된다. 2) 이때, 일의 자리가 0과 9로 끝나는 경우를 체킹해줘야한다. 0이면 1만 가능! 9이면 8만 가능! 나머진 각각 두 개씩. 3) 점화식으로 표현하면 dp[N][L] = dp[N-1][L-1] + dp[N-1][L+1] (0 N; int dp[101][10] = { 0, }; // dp[N][L]에서 N은 길이, L은 자리수 for (int i = 1; i
알고리즘/BOJ 2020. 3. 14. [C++] 백준 9095번 - 1, 2, 3 더하기 0. 문제 1. 아이디어 1) 정수 n에 대해서 1, 2, 3의 합으로 나타낼 수 있는 방법의 수는 n-1+1, n-2+2, n-3+3 을 하는 방법의 수와 같다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include int main() { int T; std::cin >> T; for (int i = 0; i > n; if (n == 1) result = 1; else if (n == 2) result = 2; else if (n == 3) result = 4; else { int* dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i = 4; i
알고리즘/BOJ 2020. 3. 13. [C++] 백준 11727번 - 2×n 타일링 2 0. 문제 1. 아이디어 1) 11726번의 풀이와 동일하다. (기본 단위를 나누는 방식이 달라질 뿐) 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include int main() { int n, result; std::cin >> n; if (n == 1) result = 1; else if (n == 2) result = 3; else { int* dp = new int[n + 1]; dp[1] = 1; dp[2] = 3; for (int i = 3; i
알고리즘/BOJ 2020. 3. 8. [C++] 백준 11726번 - 2×n 타일링 0. 문제 1. 아이디어 1) 기본 단위를 1x2 타일, 그리고 2x1 타일이 위아래로 붙어있는 모양. 이렇게 나눈다. 2) 길이가 n인 직사각형을 채우는 방법은, n-1인 직사각형에 1x2타일을 붙이는 방법 and n-2인 직사각형에 2x1 타일이 위아래로 붙어있는 모양을 붙이는 방법. 이렇게 구분하면 DP를 이용해 구현할 수 있다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include int main() { int n,result; std::cin >> n; if (n == 1) result = 1; else if (n == 2) result = 2; else { int* dp = new int[n + 1]; dp[1] = 1; dp[2] = ..
알고리즘/BOJ 2020. 3. 7. [C++] 백준 1463번 - 1로 만들기 0. 문제 1. 아이디어 1) 정수 N의 연산 횟수의 최솟값은 이전 값(N/2 or N/3 or N-1 중 최솟값)의 연산횟수에 +1한 값이 된다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #include #include int main() { std::vector v; int N; std::cin >> N; v.resize(N + 1, -1); v[0] = v[1] = 0; for (int i = 2; i

티스토리툴바