본문 바로가기

📊알고리즘/BOJ101

[👊DP뿌시기 #4] (BOJ 10844) 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 접근법 일단 N=1 ~ N=3일때 까지 무작전 모든 경우의 수를 생각해보자 DP[2]는 DP[1]에서 증가한 경우와 DP[1]에.. 2023. 8. 16.
[👊DP뿌시기 #3] (BOJ 14852) 타일 채우기 3 https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 문제 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. 접근법 저번 문제와 비슷하지만 1X1 피스가 생기면서 개복잡해졌다. N=1인 경우와 N=2인 경우는 위 그림처럼 각각 2개, 7개씩 나온다. N=3인 경우는 일단 N=2에 가로1 피스를 더한 경우와 N=1에 가로2 피스 중 (2x1, 1x1) 제외한 피스를 붙인 경우를.. 2023. 8. 15.
[👊DP뿌시기 #2] (BOJ 2133) 타일 채우기 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.\ 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 접근법 저번에 풀었던 2XN 타일링과 비슷한 문제이지만 생각해야할 점이 많다. N=1인 경우부터 보자. 블록은 최소 2개부터 시작하므로 N=1은 나올 수 없다! 그다음 N=2인 경우를 보자 이렇게 총 3가지가 나온다. N=3인 경우도 홀수인 경우 이므로 나올 수 가 없다! N=4인 경우를 보자. N=2d인 경우를 2개 붙여놓으면 .. 2023. 8. 14.
[👊DP뿌시기 #1] (BOJ 11726) 2 X N 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 접근법 처음부터 차근차근 생각해보자. 가로의 길이가 1일 때부터 생각을 해보면 다음과 같.. 2023. 8. 14.
[BOJ 1240] 노드사이의 거리 [ 접근법 ] 1. 거리를 계산하기 때문에, 거리를 저장할 2차원 배열을 만든다. 2. 다른 조건이 없으므로, 자식들을 DFS로 돌면서 자신과 목표가 같을 때 거리를 출력한다. 더보기 #include #include #include using namespace std; #define MAX 1001 vector v[MAX]; bool visited[MAX]; int parent[MAX]; int lenth[MAX][MAX]; void init() { for (int i = 1; i < MAX; i++) { visited[i] = false; } } void dfs(int start, int end, int len, int before) { visited[start] = true; if (start == .. 2023. 7. 4.
[BOJ 2644] 촌수 계산 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 전형적인 BFS 문제이다. 처음에 문제를 잘못 접근했다. 1부터 시작해서 target1과 target2의 촌수를 구해서 서로 더하면 된다고 생각했다. 그러나 다음 예외가 존재한다. 3 2 3 2 1 2 2 3 target1과 target2가 겹치기 때문에 값이 오류가 발생한다. 따라서, 시작점을 target1으로 시작해서 각 촌수를 구한 다음, target2의 촌수를 출력하면 .. 2023. 3. 31.

티스토리툴바