본문 바로가기

백준276

[Baekjoon] 2630 - 색종이 만들기 📝 문제 🔑 풀이 과정 · 처음 풀어본 분할정복 문제 · 하나의 종이가 하나의 색으로 이루어져있는지 검사한다. ① 만약 하나의 색으로 이루어져 있다면, 무슨 색 종이인지 개수를 카운팅한다. ② 만약 두 가지 색이 섞여 있다면, 가로와 세로 중간을 잘라서 4개의 색종이로 나눈다. → 이 자른 4개의 색종이에도 앞서 해왔던 과정을 한다. ▶ 이를 계속 반복해서 풀이하면 되는 것. 이는 재귀적으로 표현한다. · 탐색할때는 현재 색종이의 맨 위 왼쪽 위치를 기준으로 탐색할 것이다. 맨 위 왼쪽의 행 위치, 열 위치, 변 길이 3가지가 있으면 탐색이 가능하다. · 달아놓은 주석을 보면 풀이과정이 이해될 것이라 생각된다. 🔓 답안 import java.io.*; import java.util.StringTokeni.. 2023. 8. 17.
[Baekjoon] 1758 - 알바생 강호 📝 문제 🔑 풀이 과정 · 한 사람이 내는 팁: 원래 주려고 생각했던 돈 - (받은 등수 - 1) 등수가 뒤로 갈수록 차감되는 팁의 액수가 많아진다. 즉, 강호가 최대로 팁을 받으려면, 팁의 액수가 큰 사람일수록 앞 등수에 배치해야 한다. · 팁을 내림차순으로 정렬한 뒤, 원래 주려고 생각했던 돈 - (받은 등수 - 1) 식을 사용해서 팁의 총액을 계산한다. 주의해야 할 점은, 계산된 팁이 음수라면 강호는 팁을 받을 수 없다는 점이다. → 식의 결과가 음수라면 팁이 0원 🔓 답안 import java.io.*; import java.util.ArrayList; import java.util.Collections; public class Main { public static void main(String[.. 2023. 8. 16.
[Baekjoon] 1325 - 효율적인 해킹 📝 문제 🔑 풀이 과정 · 처음에는 예제 1이 출력이 어떻게 1, 2 나오는지 조차 이해를 못했다. 그러나 항상 그렇듯이 문제에 답이 있다. "A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다." 즉, A가 B를 신뢰하는 경우에는 B에서 A로 향하는 단방향 그래프가 생성된다는 의미이다. · 예제 1을 그림으로 표현하면 다음과 같다. 1을 해킹하면 3, 4, 5 도 다같이 해킹, 2를 해킹하면 3, 4, 5도 다같이 해킹, 3을 해킹하면 4, 5 해킹 4와 5는 해킹할때 같이 해킹되는 컴퓨터 없음. 즉 예제1의 출력이 1, 2가 되는 것이다. · N이 10,000으로 작은 편이므로 각 노드마다 BFS를 실행해준다. 물론 할때마다 방문배열 초기화는 필수다. 그리고 각 컴퓨터 해킹 시.. 2023. 8. 15.
[Baekjoon] 18352 - 특정 거리의 도시 찾기 📝 문제 🔑 풀이 과정 · 그래프를 탐색하는 문제. BFS를 사용해서 풀이했다. · 최단 거릿값을 저장하는 moves 배열을 사용했다. BFS를 사용해서 이전 도시의 최단 거릿값 + 1 을 moves 배열에 저장하는 방식을 사용했다. · 탐색 완료 후, moves 배열을 전체탐색 하면서 K값과 같은 값이 존재하면, 그 인덱스를 answer 라는 이름의 ArrayList에 저장했다. 그 후 ArrayList의 크기가 0이면 -1을 출력하고, 요소가 존재한다면 그 요소들을 출력하게 했다. · 주석을 보면 전체적인 과정이 이해갈 것이다. 🔓 답안 import java.io.*; import java.util.ArrayList; import java.util.LinkedList; import java.util... 2023. 8. 14.
[Baekjoon] 27323 - 직사각형 📝 문제 🔓 답안 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int A = Integer.parseInt(br.readLine()); int B = Integer.parseInt(br.readLine()); bw.write(A*B + "\n"); bw.flush(); bw.close(); } } 🖤 알고리즘 분.. 2023. 8. 13.
[Baekjoon] 2847 - 게임을 만든 동준이 📝 문제 🔑 풀이 과정 · 입력받은 레벨의 점수를 적당하게 감소시켜서 오름차순으로 만들어 주면 되는 문제. 즉, 배열의 요소를 다음 인덱스가 가리키는 요소보다 작게 만들면 되는 것 · 배열을 뒤부터 순회하면서, 현재 가리키는 인덱스가 i라면, 인덱스 i+1이 가리키는 요소보다 i가 가리키는 요소를 작게 만들면 된다. 나는 while문을 사용해서 이를 구현했다. · 가장 최소한으로 내리는 방법을 구해야 하므로, 작아지면 바로 다음순서로 넘어간다. (4 5 5 가 있으면 3 4 5 로 만드는게 최소, 굳이 2 4 5, 1 2 3 이런식으로 만들 필요가 없음) 🔓 답안 import java.io.*; public class Main { public static void main(String[] args) th.. 2023. 8. 12.

티스토리툴바