알고리즘

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 이 문제 또한 특정 패턴이 있다. 먼저 N은 3보다 크거나 같기 때문에 1,2 는 제외하고 보면 4와 7의 경우는 3과 5로 만들 수 없기 때문에 -1로 고정한다. if(N==4||N==7) { System.out.println(-1); } 그리고 5로 나누어 떨어지는 수는 5로 나눈 값을 출력하고 있다. 따라서 다음 코드와 같다. else if(N%5==0) { System.out.println(N/5);..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 위 문제에서 무조건 마지막 계단은 밟아야하므로 모든 구하려는 값에 마지막 계단의 수를 더해야 한다. 첫 번째 계단의 점수를 score[1] 두 번째 계단의 점수를 score[2] ... 이런 식으로 구성하고 계단이 1개일 경우의 총 점수의 최댓값 dp[1] 계단이 2개일 경우의 총 점수의 최댓값 dp[2] ... 이런 식으로 구성하였을 때 아래 사진과 같은 규칙을 보인다. dp[1] = score[1] dp[..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이 문제 또한 점화식으로 풀면 특정 규칙이 나온다. 특정 정수의 방법의 수는 n-1 , n-2 , n-3 의 수를 모두 합한 값이다. import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); int dp[] = new int[11]; dp[0]=0; dp[1]=1; dp[2]=2; dp[3]=..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 예를 들면 4의 경우 2로 나눌 수도 있고 -1을 해서 최솟값을 찾을 수 있다. 그렇게 되면 (2의 최솟값, 3의 최솟값) 중에서 최솟값을 찾아 +1 을 하면 그 숫자의 최솟값을 구할 수 있다. 5의 경우의 수 4의 최솟값+1 6의 경우의 수 ( 5의 최솟값, 2의 최솟값, 3의 최솟값 ) 중 최솟값 +1 7의 경우의 수 6의 최솟값+1 8의 경우의 수 7의 최솟값+1 ... 코드 import java.util.Scanner; public class Main{ public static void main(Stri..

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 입력 받는 n이 90보다 작거나 같기 때문에 배열 인덱스는 91까지 선언해준다. 그래야 90을 입력했을 때 값이 나오며 90번째 수는 2880067194370816120 이기 때문에 long 타입으로 선언해준다. 코드 import java.util.Scanner; public class Main{ public static void main(String[] arg..

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 합만큼 사람들을 데려와 살아야 한다. 0층의 i호에는 i명이 산다. 문제의 의미는 다음 그림과 같다. 문제의 특징은 다음 그림과 같다. 예를 들어 1층의 2호에는 0층의 2호와 1층의 1호를 합한 수랑 같고 1층의 3호에는 0층의 3호와 1층의 2호를 합한 수랑 같다. ●그리하여 각 층의 호수별 사람 수를 2차원 배열로 나타내면 [ i ][ j ] = [ i-1 ]..