본문 바로가기

전체 글1068

백준 2688 자바 - 줄어들지 않아 (BOJ 2688 JAVA) 문제 : boj2688 방법 1. dp로 풀기 dp[a][b]를 a개의 수를 가지고 표현할 때 마지막 수가 b일 경우의 수 라고 정의하자. 그럼 이 문제에 대한 dp 점화식은 다음과 같다. 즉, 개수가 하나 더 작은 경우에서(dp[a-1]), 자신보다 작은 경우들에다가 자기 자신을 붙여주면 된다. 예를들어서 현재 b가 3일 경우 001과 113뒤에 3을 붙여 0013, 1133을 만들면 조건을 만족한다. 이 점화실을 a는 1부터 입력받은 n까지, b는 0부터 9까지 진행하면 된다. 그리고 여기에 prefix sum 까지 살짝 넣어주면 시그마를 없애서 시간 복잡도를 좀 더 간소화 시킬 수 있다. 거기에 미리 최대치인 a=64까지 계산해두고, 각 T개의 n개마다 dp[n][0]+dp[n][1]+...+dp[.. 2022. 2. 3.
백준 15992 자바 - 1, 2, 3 더하기 7 (BOJ 15992 JAVA) 문제 : boj15992 1. 단순화 해서 생각해보기 우선 '사용한 수의 개수는 m개' 라는 조건이 없다고 생각해보자. 이 경우 1부터 n까지의 1차원 DP로 풀 수 있다. dp[a]를 a를 1,2,3을 더해서 표현할 수 있는 가지수라고 할 경우, 점화식은 다음과 같을 것이다. 즉, a를 1부터 n까지 증가시키며 다음의 점화식을 적용한 DP를 진행하면 된다. 2. 사용한 수의 개수가 m개 '1'에서 조건이 하나 더 추가되었다. 그러니 2차원 DP로 확장시키면 된다. dp[a][b]를 a를 1,2,3을 b번 더해서 표현할 수 있는 가지수라고 할 경우, 점화식은 다음과 같을 것이다. 마찬가지로 a는 1부터 n까지 증가시키면 되고, 이 때 b는 1부터 min(a, m) 까지 증가시키면서 구하면 된다(그냥 b도.. 2022. 2. 2.
백준 20126 자바 - 교수님의 기말고사 (BOJ 20126 JAVA) 문제 : boj20126 각 시험이 서로 겹치지 않는다는 점 때문에 상당히 쉽게 풀 수 있다. 결국 모든 시험이 겹치지 않으므로, 각 시험의 비어있는 구간이 M 이상인지만 확인하면 된다. 즉, i번째 시험을 arr[i] 라고 한다면, arr[i].x - (arr[i-1].x + arr[i-1].y) 의 값이 M보다 크다면 문제의 조건을 만족하는 시간이 된다. 예를들어 다음의 입력을 봐보자. 3 4 20 3 1 7 5 13 3 위의 그림 중 첫번째 이미지처럼 다른 시험들이 진행될 것이다. 이 때 우리가 확인해야 할 부분은 두번째 이미지의 파란 부분이다. 정렬 후 위에서 제시한 공식대로 진행한다면 어렵지 않게 찾을 수 있다. 답은 16이 될 것이다. 그리고, 그림에서도 나오듯이 주의점은 0-3 구간과 16-.. 2022. 2. 1.
백준 1439 자바 - 뒤집기 (BOJ 1439 JAVA) 문제 : boj1439 아래 에미지에서 첫줄 '11'을 바꿈으로써 그 양옆 '00'들을 한꺼번에 바꿀 수 있는 것 처럼 중간에 있는 무언가를 바꾼다면, 그 다음 더 넓은 지역을 바꾸는데 도움이 된다고 생각할 수 있다. 그래서 어떻게 생각할 지 어렵게 여겨질 수 있다. 하지만 이러한 경우에 어떻게 하든 결국 중간중간 바꾼 것과, 모든 연속된 1 토큰을 0으로 바꾸거나 모든 연속된 0 토큰을 1로 바꾸는 것 중 작은쪽은 횟수가 똑같다. 무슨 말이냐면 그냥 아래와 같이 연속된 1로 구성된 토큰의 개수와, 연속된 0으로 구성된 토큰의 개수 중 작은쪽을 출력하면 끝나는 아주 간단한 문제라는 얘기이다. (만약 '11111' 이런식이었다면 0으로 된 토큰이 0일 것이므로 0이 답) 코드 : github import .. 2022. 1. 31.
백준 18242 자바 - 네모네모 시력검사 (BOJ 18242 JAVA) 문제 : boj18242 몇x몇 짜리 사각형인지만 알면 어차피 정해진 위치에 빈 칸이 있으므로 연산을 통해 알아낼 수 있다. 이에 따라 로직을 다음과 같이 정해서 풀었다. 1. '#'이 처음 나온 줄을 찾는다. 찾은 줄에서 마지막 '#'과 첫번째 '#'의 차이를 통해 길이를 알아내고, 그 중간에 '.'이 있다면 UP 이다. 2. '1'에서 길이를 알아냈으므로 [해당 길이-2/2]만큼은 쓸모없으므로 입력을 버리고, 중앙 행을 찾는다. 여기서 좌측과 우측을 확인하여 LEFT, RIGHT를 알아낼 수 있고 마지막까지 갈 필요없이 아직까지 안나왔다면 DOWN을 출력하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader;.. 2022. 1. 30.
백준 11609 자바 - Class Time (BOJ 11609 JAVA) 문제 : boj11609 order by last asc, first asc의 형태로 정렬하면 된다. 문자열을 입력 받아 띄어쓰기를 기준으로 나눌 줄 알고, 정렬하는 방법을 안다면 쉽게 풀 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Name implements Comparable { String first, last; public Name(String name) { StringTokenizer st = new StringTokenizer(name); first = st.nextToken.. 2022. 1. 29.
백준 15922 자바 - 아우으 우아으이야!! (BOJ 15922 JAVA) 문제 : boj15922 결국 겹치는 구간은 무시하고, 모두 그려봤을 때 실제 포함되는 구간만을 구하면 된다. 이에 따라 예제 입력 1은 다음과 같이 생각해볼 수 있다. 그렇다고 배열같은거에 기입하자니 20억개나 표현이 가능해야하고, 당연히 이건 단순 순회만으로도 시간초과가 나게 된다. 따라서 내 경우엔 우선 각 x값을 기준으로 정렬한 후 현재 측정중인 구간의 시작 x와 끝점 y를 따로 기록해뒀다(코드에서 s와 e). 로직은 다음과 같다. A. x값을 기준으로 오름차순으로 정렬된 데이터를 차례대로 확인한다. 첫 s와 e는 즉 가장 x가 낮은 데이터 중 하나의 값과 동일해진다. B. 이후 각 (x,y)를 순회하면서 x가 e 이하라면 이전까지 보고 있던 (x,y)와 같은 구간으로 칠 수 있으므로 e만 조정한.. 2022. 1. 28.
백준 1817 자바 - 짐 챙기는 숌 (BOJ 1817 JAVA) 문제 : boj1817 '책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다.' 부분이 없었다면 좀 더 어려웠을텐데, 이 문제의 경우 차례대로 넣을 수 밖에 없으므로 매번 최선의 선택만 진행하면 된다. (그리디 알고리즘) 입력을 받으면서 M의 무게를 다 채울 때 까지 계속 진행하고, M이상이 되었다면 무게를 다시 리셋하고 박스의 개수를 올리는 방식을 모든 입력값에 대해 취하면 해결할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Ex.. 2022. 1. 27.
백준 2239 자바 - 스도쿠 (BOJ 2239 JAVA) 문제 : boj2239 row기준 9개, 세로기준 9개, 3x3으로 나뉜 9개에 모두 1~9가 하나씩 들어가기만 하면 된다. 따라서 로직은 다음과 같다. 1. 입력에서 0이 아닌 칸에 대해 위 3개의 조건을 체크한다. 2. 0인 칸 모두에 대해 차례대로 1~9중 들어갈 수 있는 숫자를 무작정 넣어본다. 3. 그렇게 해서 0인칸 모두를 채울 수 있는 경우가 나온다면 그대로 출력하면 된다. 그렇지 않다면 바로 직전 단계로 돌아가서 다른 수를 넣어본다.(따라서 백트래킹 문제이다.) 다음 스도쿠 이미지를 보자. 저 빨간부분에는 우선 row를 기준으로 보면(초록색 선) 아직 체크안된 값은 1과 4이다. 그리고 col기준(파란선)으로 보면 역시 1과 4가 들어갈 수 있다. 격자 기준(연두색)으로 보면 1,4,9가 .. 2022. 1. 26.
백준 2580 자바 - 스도쿠 (BOJ 2580 JAVA) 문제 : boj2580 row기준 9개, 세로기준 9개, 3x3으로 나뉜 9개에 모두 1~9가 하나씩 들어가기만 하면 된다. 따라서 로직은 다음과 같다. 1. 입력에서 0이 아닌 칸에 대해 위 3개의 조건을 체크한다. 2. 0인 칸 모두에 대해 차례대로 1~9중 들어갈 수 있는 숫자를 무작정 넣어본다. 3. 그렇게 해서 0인칸 모두를 채울 수 있는 경우가 나온다면 그대로 출력하면 된다. 그렇지 않다면 바로 직전 단계로 돌아가서 다른 수를 넣어본다.(따라서 백트래킹 문제이다.) 예를들어 기본 예제를 약간 변경한 다음 스도쿠 이미지를 보자. 저 빨간부분에는 우선 row를 기준으로 보면(초록색 선) 아직 체크안된 값은 1과 4이다. 그리고 col기준(파란선)으로 보면 역시 1과 4가 들어갈 수 있다. 격자 기.. 2022. 1. 26.

티스토리툴바