본문 바로가기

Algorithm

 (252)
[백준] 12101 : 1, 2, 3 더하기 2 JAVA 풀이 1, 2, 3을 더해서 N을 만들 수 있는 경우의 수는 1, 2, 3으로 N-1, N-2, N-3을 만들 수 있는 경우의 수를 더하는 것으로 구할 수 있다. 예를 들어 5를 만들려면 4, 3, 2에 각각 1, 2, 3을 더하면 5를 만들 수 있다. 그러니 4, 3, 2를 만드는 경우의 수를 각각 구하면 되는 것이다. 이번 문제는 N을 1, 2, 3의 합으로 나타낸 식 중 원하는 식을 출력하는 것이다. 그러기 위해서는 1부터 N까지 각자의 수를 1, 2, 3의 합으로 표현한 식이 필요하다. 하지만 숫자에 따라서 그 식의 개수는 달라지기 때문에 ArrayList를 사용했다. String형의 ArrayList 배열을 만들고, 각각의 ArrayList에는 1, 2, 3으로 그 수를 나타내는 식을 저장하는 방식이..
[백준] 10825 : 국영수 JAVA 풀이 이름과 성적들을 2차원 배열에 저장하고 람다식으로 정렬하려고 했는데 잘안됐다. Student라는 클래스를 정의하고, 인원수 만큼 객체를 생성한 다음 조건에 맞게 정렬해줬다. import java.io.*; import java.util.*; public class ArrayEx1{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 인원수를 입력받음 int N = Integer.parseInt(br.readLine()); // N명의 정보를 저장할 Student 타입의 배열 생성 Student[] students =..
[백준] 11652 : 카드 JAVA 풀이 단순히 카드의 개수를 입력받고, 그 개수만큼 카드의 숫자를 저장할 배열을 만들고 정렬한 뒤 가장 많은 카드를 출력하면 된다. 이때 카드에 적힌 숫자의 범위가 -2^62부터 2^62이므로 long 타입을 써야 한다. 1. 카드의 개수 N을 입력받는다. 2. N 크기의 카드에 적힌 숫자를 저장할 long 타입 배열을 생성한다. 3. 배열에 카드에 적힌 숫자를 저장한다. 4. Array.sort()로 정렬한다. 5. 한 숫자의 빈도수를 저장할 cnt와, 최대 빈도를 저장할 max, 빈도수가 가장 높은 수의 인덱스를 저장할 max_idx를 생성한다. 6. 정렬된 배열을 한번 쭉 돌면서 같은 숫자가 몇 번이나 나오는지 개수를 센다. 6-1. cnt가 max보다 커지면 max값을 갱신하고, max_idx를 저장한다..
[백준] 11004 : K번째 수 JAVA 풀이 입력된 수들을 배열에 저장해서 정렬한 뒤 K번째 숫자를 출력하기만 하면 되는 쉬운 문제였다. import java.io.*; import java.util.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); int[] arr =..
[백준] 11057 : 오르막 수 JAVA 풀이 만약 N = 2라면 첫 번째 자리에 0이 오면 두 번째 자리에는 0부터 9까지 총 10개가 올 수 있다. 첫 번째 자리에 1이 오면 두 번째 자리에는 1부터 9까지 총 9개가 올 수 있다. 이런 식으로 생각해보면 두 자릿수인 오르막 수는 총 55개가 된다. (10+9+....+3+2+1) 만약 N = 3이라면 첫 번째 자리가 0이면 뒤에 두자릿수는 전에 찾았던 두 자릿수의 모든 오르막 수가 되니 55개가 올 수 있다. 결국 0부터 9까지의 숫자로 만들 수 있는 오르막 수는 이전 N-1 자릿수의 j부터 9까지의 값의 합과 같다. 표를 그려보면 더 쉽게 이해할 수 있다. 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 2 10 9 8 7 6 5 4 3 2 1 3 55 45 ... ..
[백준] 11053 : 가장 긴 증가하는 부분 수열 JAVA 풀이 바로 전에 풀었던 가장 긴 감소하는 부분 수열의 길이와 전체적인 흐름은 같다. 나보다 이전에 나왔던 숫자들 중에 더 작은 숫자가 있다면, 그 숫자부터 자신까지를 포함하는 수열의 길이가 더 긴지 비교하고 값을 갱신해주면 된다. import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = ..
[백준] 11722 : 가장 긴 감소하는 부분 수열 JAVA 풀이 import java.io.*; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 수열의 길이를 입력받음 int N = Integer.parseInt(br.readLine()); // 수열을 저장할 배열 선언 int[] arr = new int[N+1]; // 감소 수열의 길이를 저장할 배열 int[] dp = new int[N+1]; // 초기화 dp[1] = 1; // 수열의 값을 입력받기 위한 스트링토크나이저 Stri..
[백준] 11726 : 2xn 타일링 JAVA 풀이 N = 4일 때까지 직접 손으로 그려보니 규칙이 보여서점화식은 쉽게 도출할 수 있었다. 하지만 계속 오답처리가 됐었는데 그 첫 번째 이유는 배열의 크기를 N+1로 선언했는데 이때 N이 1일 경우를 고려하지 않아서였다. 점화식을 사용하기 위해 dp[1]일 때와 dp[2]일 때를 초기화해줬는데, 이러면 문제가 발생해서 애초에 배열의 크기를 N의 범위+1인 1001로 바꿔주니 해결됐다. 두 번째 이유는 점화식을 계산할 때 int나 long이 담을 수 있는 범위를 넘어가기 때문이었다. 따라서 경우의 수를 구하는 그 순간에 모듈러 10007을 해줘야 정확한 값이 구해진다. import java.io.*; public class Main{ public static void main(String[] args)thro..

티스토리툴바