Algorithm/Baekjoon208 [백준] 14217: 그래프 탐색 - JAVA https://www.acmicpc.net/problem/14217 풀이도시마다 연결된 도로들이 주어진다. 도로가 만들어지고 없어지는 계획에 대한 정보가 주어진다. 계획이 주어질 때마다 수도까지 몇 개의 도시를 방문해야 갈 수 있는지 구하는 문제이다. 도시마다 연결된 정보를 이차원배열에 넣었다. 계획이 주어질 때마다 이차원배열을 업데이트하고 bfs탐색을 통해 수도 1부터 도시까지 얼마나 걸려서 갈 수 있는지 체크하여 배열에 담아 반환했다. 메모리: 49952KB시간: 1232ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n; static int[][] city; static StringBui.. 2024. 6. 20. [백준] 28449: 누가 이길까 - JAVA https://www.acmicpc.net/problem/28449 풀이HI 팀과 ARC 팀의 모든 사람들끼리 한번씩 대결하여 N X M회의 대결이 성사된다. HI팀이 이기는 횟수, ARC팀이 이기는 횟수, 무승부하는 횟수를 구해야 한다. 각 팀의 점수를 입력받아 각각 정렬했다. HI팀을 순회하면서 HI팀원의 점수를 타겟으로 하여 ARC팀에서 해당 점수와 같은 점수가 있는지 찾았다. 이때, 이분탐색을 이용하여 같은 점수가 시작되는 지점(drawStart), 같은 점수가 끝나는 지점(drawEnd)를 각각 찾았다. drawStart보다 작은 값들은 HI팀이 이기게 되고, drawEnd보다 큰 값들은 ARC팀이 이기게 된다. 메모리: 41148KB시간: 700ms언어: Java 11import java.i.. 2024. 6. 18. [백준] 2688: 줄어들지 않아 - JAVA https://www.acmicpc.net/problem/2688 풀이줄어들지 않는 수는 그 숫자의 각 자리수보다 그 왼쪽 자리 수가 작거나 같다는 것을 말한다. 예를 들어, 1234, 0011, 2223 과 같은 숫자는 줄어들지 않는 수이다. 이 문제에서는 0000과 같이 숫자의 앞에 0이 있어도 숫자로 인정이 되는 문제였다. dp를 이용해 해결했다. 이차원 배열을 만드는데, ```long[][] dp = new long[max + 1][10];``` 으로 테스트케이스의 최댓값까지 1씩 늘려가면서, 0~9까지 10개의 숫자를 확인할 수 있게 하였다. 예를 들어, ```dp[2][8]```이 의미하는 바는 2자리 줄어들지 않는 수 중 8로 끝나는 수들의 개수를 의미한다. 1자리 숫자들을 모두 1로 초기화.. 2024. 6. 12. [백준] 15809: 전국시대 - JAVA https://www.acmicpc.net/problem/15809 풀이각 국가에 군대가 있고, 국가들은 동맹, 전쟁을 통해 군대에 변화가 생긴다. 동맹을 맺으면 두 국가를 연합하여 하나의 국가로 만든다. 군대의 수는 합쳐진다. 전쟁을 하면 두 국가가 전쟁을 하여 군대의 수가 적은 국가는 속국이되고, 군대의 수는 소모된다. 두 국가가 같은 집합에 속하는지 확인하기 위해 서로소 집합을 이용했다. ``` findSet(int x)``` 메소드를 통해 해당 국가의 루트 국가를 찾는다. ``` union(int p, int q)``` 두 국가 p와 q를 동맹으로 묶는다. 군대의 수가 많은 국가를 루트로 설정하고 군대의 수를 합쳤다. ``` battle(int p, int q)``` 두 국가 p와 q가 전쟁을 벌.. 2024. 6. 11. [백준] 13206: Professor KCM - JAVA https://www.acmicpc.net/problem/13206 풀이주어진 수들의 최대 공약수를 구해야 한다. 소인수 분해를 통해 각 소수의 최대 개수를 구하고, 이를 계산했다. for (int j = 2; j * j 위의 방식으로 소인수 분해를 했다. 해당하는 소수의 개수를 map배열에 카운트해주었다. 메모리: 314872KB시간: 2580ms언어: Java 11import java.io.*;import java.util.*;public class Main { static final long MOD = 1_000_000_007L; public static void main(String[] args) throws IOException { BufferedReader br = n.. 2024. 6. 10. [백준] 14527: Paired Up - JAVA https://www.acmicpc.net/problem/14527 풀이소들의 수와 milk output이 주어진다. milk output을 기준으로 정렬했다. 투포인터를 이용하여 양쪽에서 가운데를 향해 가면서 소의 수를 감소시키고, 0이되면 다음으로 넘어간다. 이때 milk output의 합을 정답에 갱신하면 되는 문제였다. 메모리: 46184KB시간: 3044ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStream.. 2024. 6. 10. [백준] 17208: 카우버거 알바생 - JAVA https://www.acmicpc.net/problem/17208 풀이버거와 감자튀김을 조합하여 최대한 많은 주문을 처리하는 것이 목표이다. dp를 사용하여 해결했다. 주문을 처리하는 동안 남은 버거와 감튀의 수량을 고려하여 최대 주문 수량을 계산하는 배낭문제였다. 현재 주문을 포함하지 않는 경우 ``` dp[i][j][k] = dp[i - 1][j][k]```, 현재 주문을 포함하는 경우 ``` dp[i][j][k] = dp[i - 1][j - order[i][0]][k - order[i][1]] + 1``` 와 같은 점화식으로 처리했다. 메모리: 52300KB시간: 232ms언어: Java 11import java.io.*;import java.util.*;public class Main { .. 2024. 6. 10. [백준] 2015: 수들의 합 4 - JAVA https://www.acmicpc.net/problem/2015 풀이주어진 수열에서 부분 수열의 합이 k가 되는 경우를 찾는 문제이다. 누적합과 맵을 이용해 해결했다. ```sum[i]```에서 k를 뺀 값이 이전에 등장한 적이 있는지를 확인한다. 현재 누적합이 ```sum[i]```라고 할 때, ```sum[i]-k```가 이전에 등장한 적 있다면 그 구간의 합이 k라는 것을 의미한다. 메모리: 33452KB시간: 348ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br =.. 2024. 6. 10. [백준] 14863: 서울에서 경산까지 - JAVA https://www.acmicpc.net/problem/14863 풀이서울에서 경산까지 이동하는 과정에서 최대한 많은 금액을 벌기 위해 최적의 경로를 찾는 문제이다. DP를 통해 각 단계에서 걷기와 자전거로 이동할 수 있는 모든 경우를 고려하여 최대 금액을 구하는 방법을 사용했다. 각 단계에서 걷기와 자전거를 선택할 수 있다. 점화식은 다음과 같다. // 시간: walk[i][0], bike[i][0]// 금액: walk[i][1], bike[i][1]dp[i][t+walk[i][0]]=max(dp[i][t+walk[i][0]],dp[i−1][t]+walk[i][1])dp[i][t+bike[i][0]]=max(dp[i][t+bike[i][0]],dp[i−1][t]+bike[i][1]) 메모리: 57.. 2024. 6. 10. [백준] 11058: 크리보드 - JAVA https://www.acmicpc.net/problem/11058 풀이크리보드는 전체 선택, 복사, 붙여넣기, 출력 버튼이 있다. 버튼을 N번 눌러서 화면에 출력된 A개수를 최대로 하는 방법을 찾아야 한다. DP를 이용해 해결했다. DP배열을 초기화 후 DP배열을 채우면서 최적의 결과를 찾는다. for (int i = 1; i 6) { // 6번 이후부터는 복사&붙여넣기를 고려 for (int j = 3; j 메모리: 14204KB시간: 124ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 6. 10. 이전 1 2 3 4 5 6 ··· 21 다음