👨‍🏫ps/🔟0️⃣백준

[백준] 11724번 연결 요소의 개수 풀어보기 [백준]

그래프가 몇개 인지 구하는 문제였다. 나는 DFS로 풀었는데, Union-Find로 풀면 더 빠르게 풀 수 있었을 거 같다,,, 👨‍🏫 풀이 dfs로 탐색한다. 한번 dfs가 끝날때마다 graph가 하나 있는 것이다. 👨🏻‍💻 코드 package 번11724; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.lang.reflect.Array; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; public class Main { static int N, M; static Hash..

[백준] 15661번 링크와 스타트 풀어보기 [Java]

이 문제가 틀려있길래 풀었는데, 왜 틀렸었지라는 의문이 들었다.... 사람들을 두 팀으로 나눠서 능력치를 비교하여서, 최솟값을 찾는 문제이다. 각 사람들은 자기와 같은 팀을 이룬 사람과 함께 할 때 능력치가 달라진다. 팀의 능력치는 모든 쌍의 능력치 합을 구하는 것이다. (i,j)인 경우와 (j,i)인 경우 능력치가 다르기 때문에 모두 더해준다. 👨‍🏫 풀이 N : 총 인원 수 링크 팀이 1~ N/2 인원을 가질 수 있다. 그래서 1~N/2 각각에서 팀을 이룰 수 있는 경우의 수를 구해줘서 최솟값을 구하면 된다. 조합 문제처럼 풀면 된다. 👨🏻‍💻 코드 package 번15661; import java.io.BufferedReader; import java.io.IOException; import jav..

[백준] 1759번 암호 만들기 풀어보기 [Java]

조합 문제였다. 암호 조합들은 알파벳 순으로 출력을 해야된다. 암호는 모음이 최소 한개, 자음이 최소 두개로 구성되어야 했다. 👨‍🏫 풀이 들어온 알파벳들을 오름차순으로 정렬을 해주었다. 그리고 조합을 돌렸다. 모음은 1개 이상, 암호의 길이 - 2 이하이여만 했다. 그래서 해당 조건을 만족하는 암호를 출력하도록 했다. 알파벳을 오름차순으로 정렬을 해놓고, 조합을 돌렸기 때문에 암호들이 알파벳 순으로 출력되도록 풀 수 있다. 👨🏻‍💻 코드 package 번1759; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util...

[백준] 1748번 수 이어 쓰기 1 [Java]

처음에는 단순히 값을 String으로 바꿔서 더해서 length를 구하려고 했다. 이 때 생기는 문제는 100000000까지의 수가 모두 메모리에 올라가기 때문에 메모리 초과가 난다는 것이다. 그래서 각 자리 수를 계산해서 푸는 방법을 선택해서 풀었다. 👨‍🏫 풀이 해당 숫자를 10으로 나눈 값이 0이 될 때까지 나눠줘서 자릿수를 구한다. 👨🏻‍💻 코드 package 번1748; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedRea..

[백준] 17404번 RGB거리 2 풀어보기 [Java]

모든 집을 가장 적은 비용으로 색칠하는 문제이다. 조건으로는 현재 집에서 바로 전 집과 다음 집에는 다른 색을 칠해야 된다. 처음과 끝 집은 이어져 있다. 👨‍🏫 풀이 DP문제이다. 처음 집과 마지막 집을 제외하고는 이전 집의 색깔만 다르게 칠하면 조건을 만족할 수 있다. 1. 집을 색칠하기 시작할 때, 처음 집의 색깔을 정해놓고 칠한다. 2. 지금 칠하는 색과 다른 색으로 칠한 앞에 집의 값중에서 작은 것을 선택한다. 첫번째 집은 항상 미리 선택을 해놓기 때문에, 두번째 집만 첫번째 집의 색을 선택한 값으로 설정을 해놓는다. 첫번째 집과 동일한 색을 칠하는 경우는 MAX_VALUE로 설정을 해준다. return 값은 첫번째 집과 마지막 집이 같으면 안되기 때문에, 다른 색으로 칠해진 값중 작은 값을 r..