본문 바로가기

백준756

백준 1017 자바 - 소수 쌍 (BOJ 1017 JAVA) 문제 : boj1017 애초에 해결을 위한 키 아이디어도 일반적으로 찾기 쉽지 않을듯하고, 거기에 네트워크 플로우에서 이분 그래프의 최대 유량을 구하는 이분매칭 알고리즘에다가 소수 판정(에라토스테네스의 체)에다가 값 압축(이건 필수는 아님)까지 들어간 플래3에 손색이 없는 문제였다. 구현이 다소 복잡했어서 틀리면 예외찾을 엄두가 안났었는데 다행히 운좋게 한방에 통과했다. 오랜만에 한방에 통과한게 찐텐으로 기뻤다ㅋㅋ 1. 일단 브루트포스로 모든 경우를 살펴본다면 50C2번에 걸쳐 더해서 소수쌍이 되는걸 구하고, 모든 소수가 되는 쌍에 대해 모든 N개가 서로 겹치지 않고 선택되는 경우를 살펴야 한다. 대강 모든 쌍의 합이 소수가 된다면 O((50C2)!) 정도가 될 것이므로 통과할 수 없다. 서로 최대한 쌍.. 2022. 1. 4.
백준 18511 자바 - 큰 수 구성하기 (BOJ 18511 JAVA) 문제 : boj18511 N이 최대 1억이고, K의 각 원소는 1부터 9 까지이므로 어쨌든 8자리 수 이내로 모든 답이 나온다. 그리고 K는 최대 3개까지이므로 모든 경우를 봐도 최대 O(3^8) 이다. 따라서 따로 다른 방법 생각해볼 것 없이 브루트 포스로 풀면 된다. 약간의 백트래킹을 넣어서 예를들어 이미 N보다 큰 값이라면 더이상 볼 것 없이 종료하는 식으로 하면 된다. 백트래킹 개념을 넣지 않아도 시간내에 통과 가능한 간단한 문제이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private int max =.. 2022. 1. 3.
백준 10867 자바 - 중복 빼고 정렬하기 (BOJ 10867 JAVA) 문제 : boj10867 중복 제거만 하고 정렬만해도 풀 수 있는 간단한 문제이다. 해시로 중복체크하면서 list에 넣고 정렬 후 출력만 해줘도 된다. 또 다른 방법은 그냥 TreeSet에 넣으면 중복이 알아서 제거되므로 순서대로 꺼내면 된다. 내 경우엔 어차피 값이 -1000~1000 까지의 정수이므로 2000개짜리 배열에 어떤 수가 존재하는지 기입한다. 그럼 중복은 알아서 제거되고, 배열 순서대로 출력만 해주면 된다. 배열을 2001개 잡아두고 0~1000은 음수가, 그 이상은 양수가 사용하게 해도 되고, 그냥 음수 따로 양수 따로 1000개씩 배열을 만들어줘도 된다. 내 경우엔 후자로 진행했다. 예를들어 '-5 4 4 -1 -5 3 0'이 있고, 값이 -5~5 까지 가능했다고 한다면(그리기 쉽게) .. 2022. 1. 2.
백준 10465 자바 - Rolling Encryption (BOJ 10465 JAVA) 문제 : boj10465 1. 우선 문자열에서 k개를 그대로 출력한다. 이후 각 character마다 그 이전 k개의 문자열 중 가장 많이 나온 문자를 찾는다. 그리고 가장 많이 나온 문자(동일한 수가 나온게 있다면 알파벳에서 먼저 나오는걸로)만큼 쉬프트 시킨다(a면 1번, b면 2번, ..., z면 26번) 2. 문제만 보면 간단히 구할 수 있을 것 같은데, 문제는 k가 최대 10000이고 문자열의 길이가 최대 100000이므로 단순하게 각 character마다 이전 k개를 보게된다면 O(10000 * 100000)이 필요하므로 시간초과가 나게 된다. 이 경우 소문자는 총 26개이므로 별도 배열로 각 문자에 대해 세보면 더 효율적으로 가장 많이 나온 문자를 찾을 수 있다. "abbaabbac"에 대해 .. 2022. 1. 2.
백준 6588 자바 - 골드바흐의 추측 (BOJ 6588 JAVA) 문제 : boj6588 1. 홀수인 소수란 말은 그냥 2를 제외한 소수라는 의미이다. 2 말곤 전부 홀수인 소수이다. 아무튼 그러니 100만 이하의 소수를 모두 구해준다. 에라토스테네스의 체를 사용해 입력받기전에 미리 구해두면 각 케이스에 대해 해당 소수들을 써먹을 수 있으니 효율적이다. 그리고 여러 방법이 있겠으나, 시간복잡도를 좀 손해보더라도 편하게 코드를 짜기 위해 TreeSet에 찾은 소수를 넣어두었다. 시간 복잡도에 중점을 두려면 소수를 hashSet에 넣고, 추가로 소수 순서대로 배열에 넣어두면 된다. 어차피 시간이 널널한 문제라 뭘 쓰던 상관없다. TreeSet은 set이므로 a+b = n을 찾을 때 a가 정해지면 b가 존재하는지 contains(n-a)로 확인할 수 있다. 또한 hashSe.. 2022. 1. 1.
백준 10819 자바 - 차이를 최대로 (BOJ 10819 JAVA) 문제 : boj10819 N이 최대 8밖에 안된다. 8개의 수로 만들 수 있는 모든 경우를 확인해봐도 O(N!) 이므로 그냥 모든 경우를 확인해보면 된다. 재귀나 스택을 사용한 dfs로 짜면 완전탐색(=brute force)을 쉽게 짤 수 있다. 단순 반복문으로 짜려고 하면 최대 8중첩 반복문이 필요하다 ㅋㅋ 재귀에 익숙치 않다면 방문체크가 어려울 수 있다. 다음 수를 선택하기 전에(내부에서 dfs를 다시 부르면서 cnt+1 해주는 부분이 다음 수를 선택하기 위한 부분이다.) 방문체크를 하고, 반환된 후에 다시 방문체크를 해제해줘야 모든 경우를 볼 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; impor.. 2022. 1. 1.
백준 2491 자바 - 수열 (BOJ 2491 JAVA) 문제 : boj2491 1. 연속해서 커지는 경우(같은 것 포함)만 일단 생각해보자. 주어지는 N개의 숫자에 대해서, 숫자가 작아진 경우 카운팅을 1로 되돌려보자. 그럼 다음과 같이 증가(같은 것 포함)하는 경우에 대해 각 구간에서 얼마나 긴 길이를 가지는지 알 수 있다. 2. 그럼 감소하는 경우도 마찬가지다. 값이 이전보다 커지는 경우 카운팅을 1로 되돌리면서 계속 세어나가면 된다. 이 문제의 경우엔 커지거나, 작아지는 수열 중 답을 구해야한다. 하지만 다를건 없다 그냥 하나씩 입력받으면서 증가하는 경우의 카운팅과, 감소하는 경우의 카운팅을 따로따로 해주면 된다. 한번에 세지 못하고 따로따로 세줘야 하는 이유는, 모든 수가 동일한 구간이 포함된 경우 (e.g. '1 1 1 1 1 1')를 제대로 판단하.. 2021. 12. 31.
백준 2225 자바 - 합분해 (BOJ 2225 JAVA) 문제 : boj2225 1. 0부터 N까지에서 '0부터' 부분 때문에 좀 헷갈렸다. '덧셈의 순서가 바뀐 경우는 다른 경우로 센다' 라는 부분 때문에, 예를들어서 N이 1이라 해도 K가 5라면 1+0+0+0+0 / 0+1+0+0+0 / ... / 0+0+0+0+1 이 가능해진다 ㅋㅋㅋ 0의 더하는 순서라니 인지적으로는 좀 이상하긴 하지만, 사실 문제 푸는데는 상관없다! '2'를 보면 알겠지만, 그냥 1부터 N까지라고 해도 점화식이 달라질 뿐이다. 2. K-1개의 수를 합해 만든 어떠한 값이 있다. 이 값에 0부터 N까지의 정수를 더한다면 K-1개의 수로 만든 합에 1개의 정수를 더 더한 것이므로, K개의 수를 사용해 만든 어떠한 합이 될 것이다. 그렇다면 0부터 N까지의 정수를 사용해서, X개의 수를 합.. 2021. 12. 30.
백준 2133 자바 - 타일 채우기 (BOJ 2133 JAVA) 문제 : boj2133 1. 우선, 2x1과 1x2짜리 타일을 사용해야 하므로 무슨짓을 하던 n이 홀수라면 전체 칸 수(3 x n)가 홀수이므로 2칸짜리 타일로 타일링이 불가능하다. 즉, n이 짝수일 때만 타일링이 가능하다. 이 부분은 예외로 처리해준다. 2. 가장 기본적인 규칙성을 찾아보자. n=2일 때 3가지 모양이 나온다. 3. 그럼 n=4일 때는 n=2일 때 나왔던 모양에서 각각의 경우 3가지 모양이 더 추가되므로 'n=2일때의 모양 x 3'이 됨을 쉽게 알 수 있다. 예를 들어 위 n=2일때 중 첫번째 그림에 대해서만 그려보면 다음과 같다. 일단 여기까지, f(n)을 3 x n 타일링에서 n개의 가로칸으로 가능한 타일링의 경우의 수라 하자. 그럼 f(4) = f(2) * 3 임을 알 수 있다. .. 2021. 12. 30.
백준 2193 자바 - 이친수 (BOJ 2193 JAVA) 문제 : boj2193 1. N=1 일 때를 생각해보자. 0으로 시작하면 안되므로, 0으로 끝나는 수는 0개이고 1로 끝나는 수는 1개이다. (0과 1) 2. N=2 일 때를 생각해보자. 0으로 끝나려면 어떻게 해야 할까? 이 문제의 경우 1이 두번 연속으로 나오지 않기만 하면 된다. 따라서 이전 값이 0으로 끝나거나, 1으로 끝나거나 상관 없이 0을 붙일 수 있다. 반면에 끝이 1로 끝나려면 이전에 0으로 끝난 경우에 대해서만 1을 추가로 붙일 수 있다. 3. 이제 위의 규칙을 계산하기 위해 dp를 사용해보자. dp[n][x(=2)]를 n자리수에서 x로 끝나는 경우의 수라 정의하자. 이 때 n=5인 경우에 대해 그려보면 다음과 같다. 점화식으로 나타내면 dp[n][0] = dp[n-1][0] + dp[.. 2021. 12. 30.

티스토리툴바