PS/BOJ
BOJ 10825 국영수 [Java]
BOJ 10825 국영수 - 문제 링크 https://www.acmicpc.net/problem/10825 - 문제 해설 문제에서 주어진 조건대로 정렬해주는 compare 메소드를 재정의해주는 방식으로 풀었다. return 값에 따라 어떻게 정렬되는지를 신경써주면 쉽게 해결할 수 있는 문제이다. - String 클래스의 compareTo와 Integer.compare()는 왼쪽에 오는 것이 작으면 -1을, 같으면 0을, 왼쪽의 것이 더 크면 1을 리턴한다. - Comparator의 compare 메소드의 경우에는 만약 인자로 a, b를 받았다고 하자. 음수를 리턴할 경우 a가 b보다 왼쪽에, 양수를 리턴 받을 경우 b가 a 왼쪽에 위치하게 된다. 0인 경우는 a와 b가 같은 경우이다. 위 내용을 바탕으로..
BOJ 10814 나이순 정렬
BOJ 10814 나이순 정렬 자바를 이용하여 처음으로 코딩테스트 문제를 풀어보았다. - 문제 링크 https://www.acmicpc.net/problem/10814 - 문제 해설 정렬 알고리즘을 이용한 간단한 문제이다. 해결해야 하는 점은 나이가 같을 시에 순서가 뒤바뀌지 않도록 해야하는 것이다. compare 메소드를 재정의하여 풀었는데, 나이끼리만 비교하여 나이가 같을 시에 입력된 순서대로 정렬되도록 하였다. - 코드 보기 import java.io.*; import java.util.*; public class Main { static int n; public static void main(String[] args) throws IOException { BufferedReader br = new..
BOJ 11052 카드 구매하기
boj 11052 카드 구매하기 - 문제 링크 https://www.acmicpc.net/problem/11052 - 문제 해설 DP가 작은 문제부터 쌓아나가서 구하고자 하는 값을 구하는 알고리즘임을 생각하면 쉽게 접근 방법을 찾을 수 있다. 나는 보통 DP로 문제를 풀 때 D[i]를 어떻게 나눌지를 생각하는 편이다. D[i]를 i개의 카드를 사는 금액의 최댓값이라고 지정하자. 그러면 아래와 같이 쪼갤 수 있다. D[i-1] + P[1] : 카드 1개가 들어있는 팩의 구매 값 + i-1개의 카드를 구매한 최댓값 D[i-2] + P[2] : 카드 2개가 들어있는 팩의 구매 값 + i-2개의 카드를 구매한 최댓값 . . . D[0] + P[i] : 카드 i개가 들어있는 팩의 구매 값 + 0개의 카드를 구매한..
BOJ 2011 암호코드
boj 2011 암호코드 - 문제 링크 https://www.acmicpc.net/problem/2011 - 문제 해설 DP를 이용하여 간단히 풀 수 있는 문제이다. D[i]가 주어진 암호의 i번째까지에서 해석할 수 있는 가짓수라고 하자. 끝 두자리의 숫자가 10 ~ 26 범위이면 한자리 숫자 2개가 될 수도 있고 두자리 숫자 1개가 될 수도 있다는 점을 생각하면 문제를 쉽게 해결할 수 있다. 생각해볼 사항들이 무엇이 있는지 살펴보자. 암호의 처음 숫자가 0일 시에는 0을 출력한다. 맨 끝 한 자리가 0인 경우는 맨 끝 두 자리가 10, 20인 경우를 제외하고는 암호가 성립할 수 없다. 예를 들면 맨 끝 두 자리가 00, 30, 40 ... 90 같은 경우는 대응되는 알파벳이 없기에 암호가 성립되지 못한..
BOJ 2225 합분해
boj 2225 합분해 - 문제 링크 https://www.acmicpc.net/problem/2225 - 문제 해설 테이블 D[i][j]를 n이 i이고 k가 j일 때의 경우의 수라고 정의한다. 경우의 수를 어떻게 나눌지 잘 떠오르지 않아서 일단 n과 k에 따른 경우의 수를 작은 수부터 나열해보았다. 표로 나열해보면서 점화식을 유추해보자. 예를 들어 D[3][3]을 구한다고 해보자. 3을 3가지 수의 합으로 나타내는 경우는 0부터 3까지의 수를 2가지 수의 합으로 나타낸 것에다가 3이 되기위해 필요한 수를 더하면 된다. 0을 2가지 수의 합으로 나타낸 경우 : (0 + 0) 1을 2가지 수의 합으로 나타낸 경우 : (0 + 1), (1 + 0) 2를 2가지 수의 합으로 나타낸 경우 : (0 + 2), (..