하다보면 늘겠지

📍 문제 설명 A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다. 문제 N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하세요. 입력 조건 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다. (1

📍 문제 설명 N개의 동전이 주어질 때 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, N = 5이고, 각 동전이 3,2,1,1,9원이면 최솟값은 8원 또 다른 예로 N= 3 이고, 각 동전이 3,5,7원이면 최솟값은 1원 입력 조건 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다. ( 1 target = arrayList.get(0) -> 1원 동전 하나로 만들 수 있음 target += arrayList.get(0); (2) target = 2 (2원을 만들 수 있는지 확인) -> target > arrayList.get(1) -> 1원 동전 두개로 만들 수 있음 target += arrayList.get(1); (3) target = 3 (3원을 만..

📍 문제 설명 💡 접근 0을 1로 바꾸는 방법과 1을 0으로 바꾸는 방법중 최솟값을 구해야한다. 전부 0으로 바꾸는 카운트 변수, 전부 1로 바꾸는 카운트 변수 선언하고 첫번째 값에(0 or 1) 따라 카운트 변수를 증가시켜줌 이후에 선형적으로 탐색하여 바로 앞에 값이랑 같이 다르면 카운트를 증가. 0으로 바꾸는 경우에는 숫자가 1일때 count0 증가 1로 바꾸는 경우에는 숫자가 0일때 count1 증가 👩‍💻 코드 import java.util.*; public class Main { public static int solution(String s) { int answer = 0; int count0 = 0; //전부 0으로 바꾸는 경우 int count1 = 0; //전부 1로 바꾸는 경우 //첫번..

📍 문제 설명 💡 접근 0이나 1이면 더하기를 나머지이면 곱하기를 수행해주면 되겠다. 👩‍💻 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner kb = new Scanner(System.in); String s = kb.nextLine(); int result = 0; for(char c : s.toCharArray()) { //더하기 int num = c - '0'; if(num

📍 문제 설명 💡 접근 예제는 그렇게 안나왔지만 공포도가 낮은 모험가를 기준으로 모험을 보낼 수 있도록 한다. 모험가를 확인하면서 그룹에 포함된 모험가 수를 하나씩 증가시켜줌 ★★그룹에 포함된 모험가의 수 >= 해당 모험가의 공포도 이면 하나의 그룹으로 만들 수 있다. 그룹으로 만들었으면 그룹에 포험된 모험가의 수를 다시 0으로 지정해놓고 다시 반복한다. 👩‍💻 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++) ..

이 문제도 전형적으로 보텀업 방식을 이용해서 풀리는 문제이다. m원에 대한 최소 화폐 개수를 저장해놓는 d[m] 배열을 설정해놓고 화폐 단위에 따라 m원까지 탐색해나간다. 3원부터 시작해서 m원 까지 만들 수 있는 화폐 갯수 5원부터 ~ 7원부터 ~ 각 탐색시 마다 작은 값을 저장해준다. 일단 10,001이라는 값으로 초기화 시켜놓고 d[0] = 0으로 초기화시켜놓는다. 3원으로 만들 수 있는 화폐 갯수를 저장하기 위해 d[j - arr[i]] 라는 점화식을 사용한다.. 첫번째 화폐 단위는 3 d[3] = 1 d[6] = d[6-3] + 1 = 2 d[9] = d[9-3] + 1 = 3 ... 로 저장이 된다. 두번째 화폐 단위는 6 d[6] = 2와 1중에 1이 저장 import java.util.*;..

문제설명 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하여라. 입력조건 첫째 줄에 N이 주어진다.(1

DP 테이블 d[n]은 n이라는 숫자가 1이 되기위해 연산해야 하는 숫자를 의미한다. 보텀업 방식으로 2,3, ... 라는 숫자가 1이 되기 위해 필요한 최소 연산 횟수를 구하고 최종적으로 x라는 숫자가 1이 되기 위해 필요한 최소 연산 횟수를 구해본다. d[0]은 사용 안할거고 d[1] = 0 이라는 값을 이용한다. d[2]일 때 2라는 숫자가 1이 되기 위해 필요한 연산 횟수를 구해본다. 1을 빼는 경우에 d[2] = 1이 되고 2,3,5로 나누어 떨어지는 경우도 고려해본다.(1보다 작을 경우는 없긴하지만) 최종적으로 2가 1이 되기 위한 값 d[2] = 1 이 된다. d[3]일 때 3이라는 숫자가 1이 되기 위해 필요한 연산 횟수를 구해본다. 1을 빼고 2라는 숫자가 1이 되기 위해 필요한 연산 횟..

첫번째와 두번째 식량창고를 털때를 알 수가 있다. 그러면 어떻게 보텀업 방식으로 올라갈 수 있을까 생각해보자 d[0] = 3 d[1] = 1 or 3 중 큰 값으로 둔다. d[2]는 어떻게되냐면 d[0] + arr[2] 하거나 d[1]만 선택하는게 최댓값이 된다. d[2] = d[0] + arr[2] 가 됐다. d[3]은 d[1] + arr[3] 하거나 d[2]만 선택하는게 최댓값이 된다. 여기서 d[0]은 고려 안해도 되는 이유는 이미 d[2]에서 선택된 최댓값이 들어가 있기 때문이다. 점화식을 세우면 단순히 d[i] = Math.max(d[i-2]+arr[i], d[i-1]); 이 된다. import java.util.*; public class Main { public static void main..

import java.util.*; public class Main { //public static int n; //public static int m; //public static int[][] arr; public static void main(String[] args) { Scanner kb = new Scanner(System.in); //떡 갯수 int n = kb.nextInt(); //요청한 떡의 길이 int m = kb.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = kb.nextInt(); } //제일 긴 떡의 길이 int max = Arrays.stream(arr).max().getAsInt(); Syst..