백준 - 랜선 자르기 1654
2023. 4. 2. 23:22
알고리즘(BOJ)/Silver
문제 분석 완전 탐색을 하되 하나씩 움직이면 시간초과가 발생한다. 때문에 중간값을 구해서 이동 하도록 구현해야 한다. 전체 소스 import java.io.*; import java.util.*; public class Main { static int[] Arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int K = Integer.parseInt(st.nextToken()); int N = Inte..
백준 - N과M(1) 15649 (백트래킹)
2023. 3. 28. 17:45
알고리즘(BOJ)/Silver
문제 분석 겹치는 수를 제외하고 재귀를 이용해서 풀면 되는걸로 이해했다. 해당 길이가 되면 return해주고 그렇지 않다면 1씩 증가하면서 재귀를 타도록 했다. 전체 소스 package test; import java.util.*; import java.io.*; import java.util.*; public class Main { static int N, M; static int[] pick; static boolean[] visited; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(ne..
백준 - 삼각형 만들기 1448
2023. 3. 27. 17:25
알고리즘(BOJ)/Silver
문제 분석 가장 긴 변이 그다음으로 긴 2개의 긴 변의 합보다 크거나 같다면 삼각형이 될 수 없다. 때문에 정렬하여 긴변부터 그다음2개까지의 변을 합쳐 비교했다. 전체 소스 package test; import java.util.*; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int repeat = Integer.parseInt(br.readLine()); Integer[] array = new Integer[r..
백준 - 병튼 나이트 1783
2023. 3. 26. 11:42
알고리즘(BOJ)/Silver
문제 분석 개인적으로 문제 설명이 조금 부족한 면이 있다고 느꼈다. 하지만 예제가 이를 충분히 보완해주었다. 왼쪽으로 가는경우는 없기 때문에 높이에 따라 오른쪽으로 가는 칸수가 정해지게 된다. 예제1번을 보면 가로가50인데 결과가 48이다. 여기서 4개 방법을 모두 가야한다는게 한번만 그렇게 하면되는걸로 이해했다 높이1일경우 출발점을 제외하고 움직일 수 없다. 높이2일경우 2칸씩밖에 이동을 못하고 가로가 아무리 길더라도 4개 방법을 할 수 없기 때문에 최대가 4이다. 시작점, 2칸이동, 2칸이동, 2칸이동 으로 3번까지는 제약없이 움직일 수 있기 때문이다. 높이3일경우 4번 이상이면 -2를 해줘야한다 2개씩 움직이는 경우가 2번 있으니까. 직접 높이2 와 높이3에 대해서 그려보면 좀 더 직관적으로 알 수..
백준 - 타이핑 25215 (다이나믹)
2023. 3. 25. 10:39
알고리즘(BOJ)/Silver
문제 분석 직관적으로 문제에 접근하는 게 오히려 쉽게 풀렸다. 처음에는 1부터 size-1까지 해결한 후 처음과 마지막 문자열에 대한 처리를 하려고 했으나 경우의 수가 너무 많았다. 문제에 나온 것처럼 상태(◇눌린 상태인지), 현재, 다음 의 문자의 대/소문자여부를 파악하여 처리했다. 현재 소문자일 때, 소문자상태면 더 볼 것도 없이 하나의 입력만 필요하다. 현재 소문자일 때, 대문자상태면 무조건 두 개의 입력이 필요하다. 하지만 여기서 다음 문자가 소문자라면 ☆을 입력해 준 것일 테니까 대문자 상태여부는 바꿔주지 않는다 현재 대문자일 때, 대문자상태면 더 볼 것도 없이 하나의 입력만 필요하다. 현재 대문자일 때, 소문자상태면 무조건 2개의 입력이 필요하다.위에서 반대로 다음 문자가 대문자면 ☆을 입력해..
백준 1, 2, 3 더하기 9095 다이나믹
2023. 3. 23. 21:51
알고리즘(BOJ)/Silver
문제 분석 1부터 계속해서 찾아나가 보니 규칙이 보였다 앞에있던 것들로 부터 가져온다는 것이다. 내가 그린것보다 더 잘 표현된게 있어서 가져왔다. [출처] https://lotuslee.tistory.com/43 이 문제는 다이나믹 프로그래밍을 이용하여 풀 수 있다. dp 1차원 배열을 생성하고, dp[n] 는 정수 n을 1,2,3 의 합으로 나타낼 수 있는 경우의 수를 의미한다. dp[1] 은 1로만 나타낼 수 있으므로 1가지이다. n = 1 일 때, 1 한 가지이므로 dp[1] = 1 이다. n = 2 일 때, 1 + 1 2 두 가지이므로 dp[2] = 2 이다. n = 3 일 때, 1 + 1 + 1 2 + 1 1 + 2 3 총 4가지이므로 dp[3] = 4 이다. n = 4 일 때, 1 + 1 + ..
백준 - 이친수 2193 (다이나믹)
2023. 3. 18. 22:32
알고리즘(BOJ)/Silver
문제 분석 1자리 일때 1 2자리 일때 1 3자리 일때 2 4자리 일때 3 여기까지는 구하면서 그러려니 했지만 5자리 일때 5 6자리 일때 8 아! 피보나치 구나 했습니다. 이후에는 피보나치로 구현 했으나 틀렸다고..?! 한참을 고민하다가 90을 넣어보고 아.. 21억보다 크구나.. Long으로 바꿔주고 해결했습니다. 전체 소스 package test; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int input ..
백준 - 1로 만들기 1463
2023. 3. 16. 15:43
알고리즘(BOJ)/Silver
문제 분석 3가지의 경우의수에 따라서 큐에 다시 담아줘서 최소값을 구했다. 전체 소스 package test; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int input = Integer.parseInt(br.readLine()); int count = 0; Queue q = new LinkedList(); q.offer(new int[] {input,0}); int min = Integer.MAX_VALUE; ..
백준 - 물병 1052
2023. 3. 14. 21:42
알고리즘(BOJ)/Silver
전체 소스 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)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Inte..
백준 - 스네이크버드 16435
2023. 3. 10. 15:17
알고리즘(BOJ)/Silver
문제 풀이 먹을 수 있을 과일을 정렬 후 해당 수가 자신보다 작거나 같으면 size를 1늘린다. 배열의 크기 만큼 반복해준다. 전체 소스 package test; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int repeat = Integer.parseInt(st.nextToken()); int size..