문제 링크 1. 문제 풀이 BaekJoon 2231번 - 분해합 문제에서 $N$ 의 범위가 매우 커진 문제로 이전처럼 $1$ 부터 탐색하는 방식으로는 해결할 수 없다. 분해합은 생성자와 생성자의 각 자릿수의 합으로 구하는데 이때 각 자릿수는 최대 $9$ 까지만 가능하므로 생성자는 분해합에서 $분해합의 길이 - 9$ 보다는 크거나 같다는 것을...

문제 링크 1. 문제 풀이 문자열 O를 문자열 N과 같게 만들기 위해 필요한 문자열 삽입의 최솟값을 찾는 문제로 다이나믹 프로그래밍을 활용하면 해결할 수 있다. dp 테이블은 문자열 O의 $0$ 번째 인덱스부터 $i$ 번째 인덱스를 갖는 접두어와 문자열 N의 $0$ 번째 인덱스부터 $j$ 번째 인덱스를 갖는 접두어를 비교하기 위해 2차원 ...

문제 링크 1. 문제 풀이 주어진 성냥개비로 만들 수 있는 가장 작은 수와 가장 큰 수를 찾아야하는 문제로 가장 작은 수는 다이나믹 프로그래밍으로, 가장 큰 수는 그리디 알고리즘으로 찾을 수 있다. 가장 작은 수의 경우 dp 테이블은 성냥개비 $x$ 개로 만들 수 있는 가장 작은 수를 저장하면 된다. $0$ 부터 $9$ 까지 각 숫자를 만...

문제 링크 1. 문제 풀이 두 가지 연산을 통해 변환할 수 있는지 판단하는 문제로 그리디 알고리즘으로 해결할 수 있다. $S$ 를 $T$ 로 바꾸는게 아니라 반대로 $T$ 를 $S$ 로 바꿔가면 되는데 $T$ 의 끝 자리가 $A$ 면 첫 번째 연산을 통해 현재 상태가 된 것이므로 끝 자리를 제거하고, 끝 자리가 $B$ 면 두 번째 연산을 통...

문제 링크 1. 문제 풀이 세 변이 주어졌을 때, 삼각형을 분류하는 문제로 먼저 가장 긴 변이 다른 두 변의 합보다 크거나 같은지 여부로 삼각형이 될 수 있는지를 조건 분기해줬고, 이후 세 변의 길이가 모두 같은지, 길이가 같은 두 변이 있는지로 분기해줬다. 2. 코드 1. 풀이 [Java] import java.io.*; im...

문제 링크 1. 문제 풀이 주어진 성냥이 박스에 들어갈 수 있는지 판단하는 문제로 직사각형 박스에서 가장 긴 변인 대각선의 길이보다 성냥의 길이가 짧거나 같으면 들어갈 수 있다. 피타고라스 정리를 활용하면 간단하게 구할 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*...

문제 링크 1. 문제 풀이 주어진 문제에 대해 아래와 같이 각 변에 길이에 대한 변수명을 넣어줬다. 이러면 삼각형의 닯음을 활용하여 $\dfrac{w_1}{c} = \dfrac{w_1 + w_2}{h_2}$ 와 $\dfrac{w_2}{c} = \dfrac{w_1 + w_2}{h_1}$ 식을 얻을 수 있다. 위 두 식에서 좌변과 우...

문제 링크 1. 문제 풀이 두 좌표간 택시거리를 구하는 문제로 택시거리는 $x$ 좌표의 차와 $y$ 좌표의 차의 합이다. 절댓값을 통해 크기의 합을 구해야함에만 주의하면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main { pub...

문제 링크 1. 문제 풀이 2원짜리 동전과 5원짜리 동전으로 거슬러주되 동전의 개수가 최소가 되게 하는 문제로 두 동전의 최소공배수인 10원이면 5원짜리 동전 두 개로 거슬러줄 수 있어서 2원짜리 동전은 최대 4개까지만 사용하면 최소로 사용하면서 금액을 판단할 수 있다. 2. 코드 1. 풀이 [Java] import java.i...

문제 링크 1. 문제 풀이 주어진 문자열로 사전순으로 앞서는 팰린드롬을 만드는 문제로 팰린드롬은 길이가 짝수면 모든 문자가 짝수개 존재해야하고, 길이가 홀수면 홀수개 존재하는 문자가 1종류며 나머지 문자는 모두 짝수개 존재해야한다. 알파벳에 대한 카운팅 배열을 통해 각 문자의 개수를 세주고 홀수일때 짝수일때 분기처리해서 구현하면 된다. ...