본문 바로가기

ALGORITHM

 (212)
백준 17144 미세먼지 안녕! (Java) 1. 문제 링크 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받으면서 공기청정기 위치를 저장하고, 미세먼지가 있으면 전체 합에 추가한다. 미세먼지 확산과 공기청정기를 순서에 맞게 진행한다. 미세먼지 확산 후 양을 저장할 새로운 배열을 만들어서 5로 나눈 값을 사방에 저장하고, 원래 위치는 그만큼 뺀다. 모든 과정이 끝나면 확산된 배열에 있는 값을 기존 배열에 저장한다. 공기청정기는 배열 돌리기를 이용했다. 이 과정을 T초만큼 반복하면 된다. 4. 코드 impor..
백준 15683 감시 (Java) 1. 문제 링크 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 5가지 종류의 CCTV가 있고 사각지대를 최소로 만들어야 하는 문제이다. CCTV 객체 리스트를 이용해 CCTV의 위치와 종류를 저장한다. 중복순열로 CCTV 방향을 정해서 각각 방향에서 벽이 나오기 전까지 큐에 CCTV를 계속 넣으면서 진행한다. 단계가 다 끝난 후 현재 순열에서의 사각지대를 계산한다. 모든 순열이 끝난 후 최소 사각지대 수를 출력한다. 4. 코드 import java.io.Bu..
백준 1018 체스판 다시 칠하기 (Java) 1. 문제 링크 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 W인 경우를 true, B인 경우를 false로 배열을 입력 받는다. 8x8 배열 안에서 처음 값을 저장하고 반복문 돌면서 비교해서 같은 값일 때면 다시 칠해야 하니까 count를 1 더한다. 다음 값으로 비교하기 전에 boolean으로 만든 변수를 바꾸고 돌린다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import jav..
백준 1495 기타리스트 (Java) 1. 문제 링크 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 vol 배열에 시작 볼륨부터 입력받은 변경 값들을 저장한다. visit 배열을 이용해서 곡 순서와 볼륨에 true를 넣어서 중복되지 않게 한다. 0과 최댓값 사이에 있지 않은 곡 순서와 볼륨일 경우 visit 배열에 -1을 넣고 return한다. 3에서 걸리지 않으면 다음 곡으로 넘어가서 재귀를 한다. 곡의 순서가 마지막까지 오면 그때의 볼륨과 최댓값을 비교해 최댓값을..
백준 10026 적록색약 (Java) 1. 문제 링크 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 dfs로 풀었다. 적록색약인 사람과 적록색약이 아닌 사람으로 나눠서 각각 dfs를 진행했다. 적록색약인 사람은 색이 R이나 G인 경우를 함께 계산하고 적록색약이 아닌사람은 각각 따로 계산하면 된다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static StringBu..
백준 4153 직각 삼각형(Java) 1. 문제 링크 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 0 0 0 이 나올때까지 반복한다. 숫자 3개 a, b, c가 나오면 직각 삼각형이 되는 경우(아래의 3가지)에 right를 출력한다. 1. a*a + b*b == c*c 2. a*a + c*c == b*b 3. c*c + b*b == a*a 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; pub..
백준 17281 ⚾ 야구 (Java) 1. 문제 링크 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 next 변수는 다음 타자를 저장하기 위해 사용했다. flag는 3아웃 발생 시 다음 이닝으로 넘기기 위한 값이다. 순열로 타자 순서를 짠다. 4번 타자가 1번으로 던지는 경우에만 해당 코드를 반복한다. 이닝이 끝날 때 까지 해당 타자가 공을 친 결과를 확인한다. 3루부터 홈까지 루 마다 이동시키고 스코어를 더한다. 해당 값에서 최댓값이 나왔으면 최댓값으로 바꾸고 출력한다. 코드를 더 깔끔하고 효율적으로 짤 수 ..
백준 13023 ABCDE (Java) 1. 문제 링크 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 dfs를 이용해서 풀었다. 클래스를 구현해서 그 클래스로 배열을 만드는 방법 (코드 1)과 ArrayList 배열을 만드는 방법 2가지를 해봤다. 1번 방법이 확실히 코드도 간단하고 메모리나 시간 측면에서 더 나은 성능을 보여줬다. 4. 코드 방법 1 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static class Node{ public int vertex; public Node link; public ..

티스토리툴바