전체 글
-
Java 9461 파도반 수열PS 2023. 5. 22. 11:21
풀이 : dp문제는 sub문제들이 main 문제를 해결해주기 때문에 해당 규칙을 찾아내기 위해 수열을 나열해주었고 나열한 수열에서 i번째에 오는 수는 i-2 + i-3 이란 식을 도출해내었고 이를 memoization해주어 값들을 구한 뒤 입력받은 N을 출력해주었다. int형으로 값을 받으면 사이즈가 초과되니 long형으로 받아주었다. 처음엔 dp문제 푸는 게 너무 막막했는데 꾸준히 계속 풀다보니 요령이 조금 생기는 거 같아서 뿌듯했다. top-bottom, bottom-top 두가지 방식으로 풀어보았다. bottom-top import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public..
-
Java 1149 RGB거리PS 2023. 5. 13. 00:23
풀이 : 같은 색깔의 집이 연속하면 안된다는 조건만 잘 지키면 어렵지 않게 풀 수 있는 문제였습니다. 그리고 처음 시작하는 경우가 3가지 있기 때문에 각각의 시작점에서 구한 최소값들을 비교하여 그 중에서 제일 작은 값을 출력하면 됩니다. dp문제이기에 메모이제이션을 할 배열을 선언하고 최종값에 도달하기 전까지의 값들을 저장해주며 연산을 이어나가면 됩니다. dp문제를 풀 때는 내가 당장 어떤 조건문이나 반복문을 통해 원하는 값을 한방에 도출해낸다는 생각보단 내가 원하는 값들을 도출할 수 있는 식을 세워서 그 식들이 내가 원하는 값을 구해준단 생각을 가지고 접근하는 게 중요하고 dp 문제가 어려우신 분이라면 제일 중요한 건 많이 풀어봐야 감을 잡을 수 있습니다. import java.io.BufferedRe..
-
Java 1145 적어도 대부분의 배수PS 2023. 5. 11. 20:42
풀이 : 브루트포스 알고리즘의 문제로서 단순히 값이 나올 때 까지 계산하여주어 풀었습니다. 3개의 수에서 가장 큰 값을 기준으로 3개의 값이 나누어떨어지는 값을 찾으면 되는 문제였습니다. 3중 for문으로 탐색 범위를 정한 뒤 while문에서 조건에 맞는 값을 찾아주었습니다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReade..
-
Java 2941 크로아티아 알파벳PS 2023. 5. 6. 02:40
풀이 : 그냥 구현하는 문제인 거 같아서 조건식에 맞춰서 알파벳의 수를 +-하는 식으로 풀이하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); int count = 1; // 알파벳 갯수 for(int i = 1; i < str.length(); i++){ swi..
-
Java 1929 소수 구하기PS 2023. 5. 5. 16:16
풀이 : 입력 값이 1,000,000 까지기 때문에 범위를 1,000,000까지 잡고 소수를 구하게 되면 시간내에 수행할 수 없는 문제이다. 범위를 n의 제곱근 값까지만 설정한 뒤 계산하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringToke..
-
Java 1920 수 찾기PS 2023. 5. 5. 01:17
풀이 : 이분탐색을 하는 메서드를 구현한 뒤 둘째줄에서 입력받은 배열에 네번째 줄에서 받은 배열의 숫자가 있는지 이분 탐색을 이용하여 확인한 뒤 출력하면 풀 수 있는 문제다. 이분 탐색이란, 처음부터 끝까지 비교하며 찾는 선형검색 방법과는 다르게 배열의 시작부터 끝까지의 크기에서 2를 나누어 기준을 잡은 뒤 타겟값과 기준 값을 비교하여 시작과 끝을 좁혀가며 원하는 값을 찾는 방법으로 글로 보는 거보단 그림과 코드로 보는 편이 이해가 더 잘되었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.A..
-
Java 17299 오등큰수PS 2023. 5. 4. 16:56
풀이 : 오큰수 문제와 유사하다. 오큰수는 자신의 오른 쪽에 있는 큰수를 찾는 것이었다면 오등큰수는 자신의 오른쪽에 자신의 등장횟수보다 큰 수를 찾는 것이다. 없으면 -1로 표시한다. 오큰수 문제에서 조건만 바꾸면 되는 것이라 간단하게 풀 수 있었다. arr배열 : 수열을 저장한 int형 배열 cnt배열 : 수열에 있는 수가 등장한 횟수 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class Main { public static void main(String[] arg..
-
Java 17298 오큰수PS 2023. 5. 4. 16:22
풀이 : 오큰수란 자신의 오른쪽에 있는 자신보다 큰 수를 말한다. 예를 들어 3, 5, 2, 7 란 수열이 있을 때 3을 기준으로 5가 가장 가까운 큰수이기에 3의 오큰수는 5가 된다. 문제를 이해하고 시간제한을 확인하지 않고 이중for문을 사용하여 풀이하다가 시간초과가 나버렸다 ... 그래서 이중for문이 아닌 while문으로 스택을 활용하여 풀이하였다. 우선 주어진 수열을 for문으로 array에 초기화 해준 뒤 arr라는 int형 배열타입에 저장해주었다. 그리고 첫번째 원소는 무조건 비교대상이 되어야하니 stack에 0을 푸쉬해주었다. for문을 첫번째 원소는 푸쉬해두었으니 1부터 arr.length까지 진행하고 그 안에 while문으로 stack이 비어있지 않고, 스택의 top이 arr[인덱스]..