전체 글1321 [백준] 11052 카드 구매하기 - Dynamic Programming / Java • 문제 링크 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net • 풀이 과정 n 이 주어지고 0 ~ n 의 범위의 각각의 정수의 합이 n 되는 조합의 규칙성을 찾는 문제. 예시로 n = 4 일 때 4 = 0 + 4 = 1 + 3 = 2 + 2 = 3 + 1 의 규칙이 존재하고 이를 더 세분화하면 4 = (4 - 4) + 4 = (4 - 3) + 3 = (4 - 2) + 2 = (4 - 1) + 1 로 나타낼 수 있다. 이때 괄호 안의 첫 항과 둘째 항의 값과 대응되는 항을 각각 i, j 로 치환 시 2중 for 문으로.. 2022. 7. 19. [백준] 9095 1, 2, 3 더하기 - Dynamic Programming / Java • 문제 링크 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net • 풀이 과정 규칙성을 발견하기 위해 n이 1 ~ 4 일 때 1, 2, 3 의 합으로 나타내는 경우의 수을 표현하면 아래와 같다. n = 1 (1) n = 2 (1 + 1) (2) n = 3 (1 + 1 + 1) (1 + 2) (2 + 1) (3) n = 4 (1 + 1 + 1 + 1) (1 + 1 + 2) (1 + 2 + 1) (2 + 1 + 1) (2 + 2) (1 + 3) (3 + 1) 위와 같이 n = 4 일 때 모든 경우의 수는 1 ~ 3 의 모든 경우의 수를 포함한다. 이에 대한 점화식을 dp 배열을 활용한 코드에 적용하면 dp[i] .. 2022. 7. 18. [백준] 11726 2×n 타일링 - Dynamic Programming / Java • 문제 링크 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net • 풀이 과정 문제에서 제시된 직사각형의 세로의 길이는 2로 고정되어 있으므로 가로의 길이만 고려하여 점화식을 구한다. 즉 n 을 1 또는 2의 합으로 나타내는 방법의 수를 구하는 문제로써 예시를 나타내면 아래와 같다. 2 = (1 + 1) (2), 3 = (1 + 1 + 1) (1 + 2) (2 + 1), 4 = (1 + 1 + 1 + 1) (1 + 1 + 2) (1 + 2 + 1) (2 + 1 + 1) (2 + 2) 이때 4를 만드는 경우의 수는 2의 모든 경우의 수.. 2022. 7. 17. [백준] 1463 1로 만들기 - Dynamic Programming / Java • 문제 링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net • 풀이 과정 1 ~ n 까지의 각각의 수를 문제에 제시된 조건에 맞는 연산을 하여 최소 연산이 되는 횟수를 저장할 dp 배열을 n + 1 의 크기로 생성한다. i가 1 ~ 10 의 범위일 경우 i - 1, if (i % 2 == 0) i / 2, if (i % 3 == 0) i / 3 의 연산 중 최소 횟수의 연산을 각각의 dp 배열 인덱스에 저장하면 아래와 같다. 0 1 2 3 4 5 6 7 8 9 10 11 0 0 1 1 2 3 2 3 3 2 3 - 예를 들어 n = 6 일 경우 문제에 제시된 3가지 연산이 모두 가능하며, i - 1 = 6 - 1 = 5,.. 2022. 7. 16. [백준] 2644 촌수계산 - Graph Theory / Java • 문제 링크 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net • 풀이 과정 문제에 제시된 촌수는 연결 요소에서 특정 두 정점 간 도달하기 위한 간선의 개수를 의미한다. 정점의 개수, 거리를 계산할 두 정점, 그리고 무향 그래프 정보를 입력받아 인접 리스트로 구현한다. 시작 정점을 지정해 dfs 탐색을 수행할 함수에 매개변수로 전달하고, 간선을 따라 이동한 횟수를 나타낼 cnt 변수를 매개변수로 0으로 초기화하여 생성한다. 방문 여부를 확인하는 boolean 배열을 활용하여 연결된 모든 정.. 2022. 7. 15. [백준] 11403 경로 찾기 - Graph Theory / Java • 문제 링크 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net • 풀이 과정 모든 정점에서 모든 정점으로의 최단 거리를 구하고 정점의 개수가 1 ≤ N ≤ 100 수준이므로 플로이드 와샬 알고리즘을 활용하여 풀이한다. 기본적으로 거쳐가는 정점을 기준으로 최단 거리를 구하며 거쳐가는 정점이 k 일 경우 i 에서 j 로 도달하는 거리와 i 에서 k를 거쳐 k 에서 j 로 도달하는 거리는 같다는 전제를 둔다. 즉 k, i, j 의 3중 for문 내에서 arr[i][k] == 1 && arr[k][j] == 1 인 경우에만 arr[i][j] = 1 로 모든 정.. 2022. 7. 14. 이전 1 ··· 203 204 205 206 207 208 209 ··· 221 다음
