본문 바로가기

분류 전체보기

 (215)
백준 1717 집합의 표현 (Java) 1. 문제 링크 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 makeSet으로 서로소 집합을 만들고, 입력 받은 명령어가 0인 경우 union으로 합집합을 만들고, 그 외 명령어이 경우 findSet을 이용해 두 집합이 부모가 같은지 확인한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..
백준 2805 나무 자르기 (Java) 1. 문제 링크 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 나무 높이 범위가 매우 커서 이분탐색으로 풀었다. 최댓값과 자른 값의 중간 값을 이용해 중간값보다 큰 나무에서 그만큼 베어간다. 자른 나무의 합이 원하는 값인 M보다 작으면 높이를 낮춰야 하니까 현재 최댓값을 중간값으로 넣고 반복한다. 만약 자른 나무의 합이 M보다 크거나 같아지면 중간값보다 하나 큰 값을 넣고 반복한다. 뭔가 하나씩 풀어쓰려니까 애매한데 자른 값이 ..
백준 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..

티스토리툴바