백준 - 램프 1034
2023. 4. 4. 23:55
알고리즘(BOJ)/Gold
문제 분석 1. 모든 행의 0 의 개수를 파악한다. 1-1. 0의 갯수가 파악되야 K번의 반복으로 다 킬 수 있는 상황인지 알 수 있다. 2. 반복되는 K가 짝수 인지 홀수 인지 파악한다. 2-1. 홀/짝이 파악되야 똑같은게 가장 많은 행들의 램프를 킬 수 있는지 알 수 있다. 3. 파악된 0의 갯수가 K보다 이하인지, K와 같은 홀/짝 인지 파악한다. 전체 소스 package test; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(..
백준 - 랜선 자르기 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; ..
백준 - 저울 2437
2023. 3. 15. 23:32
알고리즘(BOJ)/Gold
문제 분석 처음에는 경우의수를 DFS로 구하려다가 알고리즘 분류 힌트를 보고 안쓰고 풀 수 있다는 방법이 있다는것을 찾아야했다. 아무리 생각해도 모르겠어서 다른 사람 풀이방식만 참고했다. 누적된 수의 +1 보다 다음수가 크다면 안된다는 것이다 sum+1 >= array[i] 를 만족해야 한다는 것이다. 처음에 sum은 +1까지하면 1이니까 첫번째 수가 1보다 큰 수가 오면 안될것이다 그다음 누적의 수는 2 인데 2보다 큰수가 오면 조합이 안된다. 전체 소스 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new B..