본문 바로가기

백준756

백준 2294 자바 - 동전 2 (BOJ 2294 JAVA) 문제 : boj2294 1. 우선 문제에서 필요없는 정보를 제한해보자. 1.1 '사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.' -> 이 조건은 해당 가치를 표현하는 경우의 수를 구할때나 의미가 있다. '사용한 동전의 최소 개수'를 구하는 문제이므로 무시해도 된다. 1.2 '가치가 같은 동전이 여러 번 주어질 수도 있다.' -> 가치가 동일한 동전의 경우 연산을 느리게 할 뿐이므로, 동일한 동전이 주어진 경우는 HashSet 등을 사용해 제거하면 될 것임을 생각할 수 있다. 1.3 'k 2021. 12. 30.
백준 2293 자바 - 동전 1 (BOJ 2293 JAVA) 문제 : boj2293 1. 우선 문제를 좀 더 간단히 변경해서 봐보자. 1,2,5의 가치를 가지는 동전이 있고, 그 가치의 합이 10이 되게 하려 한다. 그리고 문제와 다르게 동전의 구성이 같아도 순서가 다르면 다른 경우로 치고 생각해보자. 그럼 1차원 배열을 활용한 dp로 아래와 같이 풀 수 있다. (냅색 문제처럼 풀면 된다.) 1.1 우선 초기값이다. dp[idx]는 1,2,5의 동전들을 가지고 idx의 가치를 가지는 경우의 수를 나타낸다. dp[0]은 실제론 불가하지만, 초기값으로 넣어준다. 그래야 동전 하나를 가지고 표현할 수 있는 경우에 대해서도 별도로 처리하지 않고 점화식 하나로 계산하기 편하다. (예를들어 2의 가치를 표현하려면 동전2짜리 하나만 쓸 수 있다. 식으로는 dp[2-2]이다. .. 2021. 12. 29.
백준 2757 자바 - 액셀 (BOJ 2757 JAVA) 문제 : boj2757 R값은 그냥 그대로 출력하면 된다. C값의 경우, 10진수를 26진수로 변경한다고 생각하면 좀 편하게 생각할 수 있다. C값은 뒤부터 한 자리씩 26으로 나눠보면서 맞는 문자를 매칭시키는 방식으로 찾을 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder answ.. 2021. 12. 28.
백준 2012 자바 - 등수 매기기 (BOJ 2012 JAVA) 문제 : boj2012 1. 흔히 생각해볼만한게, 예를들어 '1 8 4 5 6'과 같은 입력이 있는 경우 총 1~5등 까지를 매칭시켜야 한다. 그렇다면 1~5등 사이 중 일단 자기가 원한 등수가 가능한 녀석들을 매칭시키자. 그럼 1, 4, 5는 1~5등 내에 매칭이 가능할 것이다. 이제 8과 6이 남는데, 당연하게도 정렬해서 매칭시키는 것이 더 정답에 가까울 것임을 유추할 수 있다. 따라서 정렬 후 차례대로 남는 위치에 매칭시키면 답을 구할 수 있다. '1'의 방법을 정리하면 1.1 N을 입력받는다. 1.2 1~N에 바로 매칭이 가능한 예상등수를 매칭시킨다. 1.3 남는 등수를 정렬한 후, 1~N 사이 남는 등수에 매칭시킨다. 이 된다. 2. 그런데 사실 더 쉬운 방법이 있다. 어차피 (|A-B|)의 합.. 2021. 12. 27.
백준 20127 자바 - Y-수열 (BOJ 20127 JAVA) 문제 : boj20127 증가수열 또는 감소수열인 것은 해결 로직을 세우는데에 상관이 없다. 증가수열, 감소수열 둘다 별도 로직으로 계산한다고 생각하면 그 중 작은걸 출력하면 된다. 기본적으론 이런데, 이 문제의 경우 정답률이 낮은만큼 많은 경우를 세세하게 예외처리해줘야 통과할 수 있다. 이하 여러가지 케이스에 대해 설명해본다. 1. 기본 로직은 증가수열을 체크한다면 수가 작아지는 부분을, 감소수열을 체크한다면 수가 커지는 부분의 개수가 2개 이상이라면 증가 혹은 감소수열이 될 수 없다. 예를들어 '예제 입력 1'에 대해 증가수열로써 체크한다면 감소하는 경우가 1번 이하이므로 가능하다! 하지만 감소수열로써 체크한다면 감소하는 경우가 2번 이상이므로 감소수열로는 만들 수 없다. 2. 이번엔 '1'와 같은 .. 2021. 12. 26.
백준 10997 자바 - 별 찍기 - 22 (BOJ 10997 JAVA) 문제 : boj10997 1. 일단 규칙부터 유추해보자. 대강 n이 주어질 때 우측상단부터 시작해서 n-0.5 바퀴 돌리는 별찍기라 볼 수 있다. 예를들어 3이라면 2.5바퀴를 돌린 형태이다. 2. 좀 더 구체적으로 짤 수 있는 로직을 생각해 보자면, 1일 때는 그냥 예외로써 '*' 하나만 출력해주면 되겠고, n이 2 이상이라면 row의 개수는 3+4*n, column의 개수는 1+4*n 이 된다. 그리고 우측 상단부터 시작해서 좌,하,우,상의 방향을 순서대로 돌리면서 갈 수 있는 곳까지 별을 찍으면 된다. 갈 수 있는 조건은 배열의 끝 혹은 가려는 방향으로 2칸 앞이 이미 별인 경우 해당 위치까지만 찍을 수 있다. 즉 row와 column 개수에 대한 점화식만 잘 세우고, 그 이후로는 단순 구현으로 풀.. 2021. 12. 25.
백준 4485 자바 - 녹색 옷 입은 애가 젤다지? (BOJ 4485 JAVA) 문제 : boj4485 1. 젤다가 활강하는 장면! 야숨2가 나오면 알고리즘을 당분간 못(안)풀 수 있으니 알고리즘을 미리 풀고 키핑해둬야겠다ㅋㅋㅋ 2. 만약 이런식의 문제에서 이동 가능한게 좌측과 아래쪽 뿐이었다면 DP로도 풀 수 있다. 하지만 이 문제와 같이 4방향으로 이동이 가능하다면, DP로 풀어보려면 결국 모든 경우를 다 봐야해서 시간초과가 나게 될 것이다. O((N^2)^2) 한가지 떠올릴만한 점은 결국 배열도 그래프라는 것이다. 예제 입력의 아래와 같은 부분을 그래프 형태로 그려보면 다음과 같다. 3 5 5 4 3 9 1 3 2 7 결국 이 문제는 가장 적게 잃으면서 진행해야 하므로, 그냥 그래프에서 start부터 goal 까지의 최단거리를 찾는 것과 동일하다! 그리고 가중치가 모두 양수이면.. 2021. 12. 24.
백준 2670 자바 - 연속부분최대곱 (BOJ 2670 JAVA) 문제 : boj2670 1. 모든 경우를 보면서, 이전 값이 1.0 보다 크다면 현재 입력받은 수를 곱해준다. 이전까지 구해둔 값이 1.0 이하라면 현재값을 곱하는 것이 손해이므로, 현재값부터 다시 연속된 수를 파악하면 된다. 예를들어 1.2 0.9 1.5 가 있고 현재 1.5를 살펴볼 차례라고 해보자. 이전까지의 값의 곱인 1.2*0.9는 1.08이므로 1.0보다 크다. 따라서 1.5까지 곱해서 1.620이 답이 된다. 반면에 1.1 0.9 1.5라면 1.1*0.9 = 0.99 이므로 1.5에 곱하면 오히려 손해이다. 따라서 1.5부터 다시 구해나가는 것이 더 이득이다. 정리하면 현재 입력받은 수가 cur, 이전까지 계산하던 값이 bf 라고 해보자. bf>1.0이라면 bf = bf * cur이 될 것이.. 2021. 12. 23.
백준 9001 자바 - Rectangle Coloring (BOJ 9001 JAVA) 문제 : boj9001 1. 우선 그룹의 개수는 어떻게 구할 수 있을까? 그룹 구하는데 특화된 union-find (분리 집합) 알고리즘을 사용하면 쉽게 그룹이 총 몇개인지 알 수 있다. 2. 그럼 입력받은 직사각형들에 대해 모든 경우를 다 보면서 O(N*N) 서로 직사각형이 겹치는지 여부만 알 수 있다면 union-find로 그룹으로 만들어주고, 최종적으로 그룹의 개수를 출력해주면 된다. 직사각형 겹치는걸 확인하는데 가장 쉬운 방법은 배열에 직접 직사각형에 포함된 면적을 기입하면서 겹치는지 확인하는 것인데, 문제는 이 경우 최대 O(N*10000*10000) 이 걸리므로 불가하다. N이 최대 200인것에 착안해 좌표 압축을 통해 해봐도 된다. 그럼 최대 O(N^3)이면 구해볼 수 있다. 내 경우엔 그냥.. 2021. 12. 22.
백준 14002 자바 - 가장 긴 증가하는 부분 수열 4 (BOJ 14002 JAVA) 문제 : boj14002 가장 긴 증가하는 부분 수열의 길이 자체는 이분탐색을 활용한 LIS 알고리즘을 쓰면 얻을 수 있다. 하지만 LIS 알고리즘은 가장 긴 증가하는 부분 수열의 '길이'를 파악할 뿐이고, 이 문제에서는 가능한 수열 중 하나를 출력하는 방법도 찾아야 한다. LIS 알고리즘에 대한 설명은 생략하고, 가능한 수열을 찾는 방법에 대해 설명한다. 1. LIS 알고리즘에서 입력이 10 20 30 5 15 가 들어오면 어떻게 될까? 최종적으로 LIS의 길이인 '3'은 구해낼 수 있으나, 배열에는 다음과 같이 '5 15 30' 이라는 값이 들어가 있게 된다. 실제 정답은 '10 20 30'이므로 LIS 알고리즘 자체만 사용해서는 원하는 실제 수열을 출력할 수 없다. 2. 추가로 배열을 더 사용해서 .. 2021. 12. 21.

티스토리툴바