알고리즘/백준48 [백준 16194] 카드 구매하기 2 - 자바 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1. 풀이 이 문제는 [백준 11052] 카드 구매하기 - 자바와 거의 똑같은 문제이다. 이번엔 카드 N개를 구매하는데 최소 비용을 고르는 문제이다. 주의할 점은 처음 배열을 선언하면 초기값이 0이므로, 배열의 초기값을 잘 설정해줘야한다. 그래서 카드 N개를 구하는 비용을 카드가 N개 들어있는 카드팩으로 초기 설정해주면 쉽게 풀 수 있다. 백준님의 경우는 배열의 초깃값을 입력값의 최대 개수와 비용의 .. 2020. 5. 2. [백준 11052] 카드 구매하기 - 자바 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1. 풀이 보통 DP의 경우 경우의 수를 구하는 경우가 많아 처음엔 다른 방식으로 풀어보다 백준 강의를 통해 DP로 푸는 방법을 알 수 있었다. 카드 N개를 구매하는데 드는 비용의 최대값을 구하면 되는 문제이다. 이를 점화식으로 표현하기위해서 다음과 같은 식이 나온다. 카드 N개의 최대비용을 구한다면, 아래식을 반복하면서 최대값을 구한다. 카드 1개가 들어있는 카드팩을 구매한다면, 카드 N-1개를 구매한.. 2020. 5. 2. [백준 11727] 2xn 타일링 2 - 자바 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 1. 풀이 [백준 11726 2xn 타일링] 와 거의 똑같은 문제이다. 하지만 조건에서 2x2의 타일도 가능하다했으므로 점화식을 세워보면 D[n] = D[n-1] + D[n-2] + D[n-2]가 나오는 것을 볼 수 있다. 2. 코드 import java.util.*; public class Main { static int[] memo = new int[1001]; static int tile2(int n){ if(memo[n.. 2020. 5. 1. [백준 17103] 골드바흐 파티션 - 자바 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 1. 풀이 골드바흐의 추측과 거의 똑같은 문제이다. 주의 할 점은 두 소수의 순서만 다른 것은 같은 파티션으로 본다는 것이다. 우선, 에라토스테네스의 체를 이용해 MAX까지 소수를 구하고 나서, 두 소수의 순서가 바뀐 것은 count해주지 않으면 된다. a와 b가 N을 구성하는 소수라면, a를 N/2이하까지만 탐색하면 된다. 즉, N이 10이라면, 10의 1/2인 5까지만 탐색을 해주면 된다. 그 .. 2020. 5. 1. [백준 17087] 숨바꼭질 6 - 자바 https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다. 모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자. www.acmicpc.net 1. 풀이 수빈이와 동생의 거리들의 최대공약수를 구하는 문제. 수빈이는 이동을 X+D, X-D로만 가능하고, 하나의 D로 모든 동생을 찾아야 한다. 이 문제는 수빈이와 모든 동생들의 거리를 구한 다음, 거.. 2020. 4. 30. [백준 9613] GCD 합 - 자바 https://www.acmicpc.net/problem/9613 9613번: GCD 합 문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다. 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. 예제 www.acmicpc.net 1. 풀이 입력 값들을 받고 입력 값들끼리 반복문을 돌면서 두 개씩 짝을 지어 GCD(최소공배수)를 구해서 다 더해주면 되는 문제입니다.. 2020. 4. 30. 이전 1 2 3 4 ··· 8 다음
