본문 바로가기

Algorithm/BOJ

 (101)
[BOJ-14501][DP] 퇴사 - Java 문제 바로가기 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 딱 보자마자 DP로 풀면 되겠구나 싶었습니다. 하지만 N의 최댓값이 15기 때문에 완전 탐색해서 풀어도 되고 DFS로 풀어도 됩니다. 저는 DP를 잘 못하기 때문에 열심히 짱돌굴려서 풀어보았습니다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br ..
[BOJ-14500][시뮬레이션/DFS] 테트로미노 - Java 문제 바로가기 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 블럭 네 개짜리 테트로미노를 만들어서 입력으로 주어진 맵에 테트로미노에 해당하는 구역의 합이 젤 큰 값을 구하는 문제입니다. 여러 방법으로 블럭을 만들 수 있습니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static class..
[BOJ-14499][시뮬레이션] 주사위 굴리기 - Java 문제 바로가기 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 일반적인 시뮬레이션 문제입니다. 마찬가지로 주어진 제한 조건들을 잘 고려해서 풀어야 합니다. 삼성 SW 역량 테스트 문제가 점점 어려워지는 것 같습니다.. 최근에 나온거 보다가 윗 쪽에 있는 거 보면 선녑니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..
[BOJ-13458][시뮬레이션] 시험 감독 - Java 문제 바로가기 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 기본적인 로직은 어렵지 않은 문제입니다. 다만 변수에 들어갈 수 있는 최댓값을 고려해서 자료형을 정해줘야 합니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public stat..
[BOJ-12100][시뮬레이션/스택] 2048 (Easy) - Java 문제 바로가기 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 다들 많이 해봤을 법한 게임 2048을 구현하는 문제입니다. 주어진 초기 판을 최대 다섯 번 움직여서 나올 수 있는 최댓값을 구하는 문제입니다. 문제에는 '최대 다섯 번' 움직였을 때라고 나오지만 게임을 진행하는데 한번 더 움직인다고 해서 최댓값이 줄어들진 않기 때문에, 그리고 다섯 번 다 움직였을 때 최댓값이 나올 수 있으므로 무조건 5번 움직이고 나서 값을 구해주면 됩니다. import java.io.BufferedR..
[BOJ-1717][Disjoint-Set] 집합의 표현 - Java https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net Disjoint-Set 을 사용하는 가장 기본적인 문제라고 생각합니다. p[] 배열을 만들고, find() 연산과 union() 연산을 이용하면 쉽게 풀 수 있습니다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public cl..
[BOJ-2468][BFS] 안전 영역 - Java 문제 바로가기 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 전형적인 BFS 문제입니다. 물에 잠기는 높이마다 체크해주면 됩니다. import java.io.*; import java.util.*; class Dir{ int y, x; Dir(int y, int x){ this.y = y; this.x = x; } } public class Main { static int N; static int[] dy = {1, -1, 0, 0}; static int[] dx = {0, 0, 1, -1}; static in..
[BOJ-17471][BFS] 게리맨더링 - Java 문제 바로가기 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net N개의 구역이 주어지고 인접한 구역들을 묶어서 두 개의 선거구를 만듭니다. 두 선거구의 인구 차이의 최솟값을 구하는 문제입니다. 부분집합을 만들고 BFS로 인접한지 탐색했습니다. import java.io.*; import java.util.*; public class Main{ static final int MIN = 9999999; static int[] population; static boolean[] isSelected; static int N; static i..

티스토리툴바