www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 처음에 네트워크를 구하는 줄알고 dfs인 줄 알았으나 depth (친구의 친구)가 2인 곳까지만 탐색하므로 bfs로 풀었다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n,m; static ArrayList[]..
www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } public class Main { static int n,m; static int[][] map; static in..
www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 미친 구현.. ㅎㅎ 옅은 영역과 보드가 모두 차는 경우 점수 계산 먼저하고 옅은 영역을 처리해준다. 이때 행을 밀게 되는데 옅은 영역번호 0,1 행 혹은 열에 해당하는 곳을 꼭 0으로 초기화해줘야된다. 점수를 계산할 때도 옅은 영역을 포함해서 밀어주되, 행 혹은 열이 0인 곳은 덮어씌워지지않으므로 꼭 0으로 초기화를 해줘야 된다. 나머지는 구현구현 import java.util.Scanner; pub..
www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 상어 주의할 점 사방에 냄새가 있을 경우 자기의 냄새 방향으로 간다. (자기의 냄새도 사방에 있을 수 있다. 여기서도 우선순위대로 처리해주자.) import java.util.Scanner; class Place{ int y,x; public Place(int y, int x) { super(); this.y = y; this.x = x; } } public clas..
www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 자신의 번호가 들어갈 수 있는 배열을 하나 만든다(0 초기화) 그리디 탐색으로 보고있는 자리가 비워져있다면 나보다 큰 사람이 들어갈 곳으로 판단해서 cnt를 1감소시킨다. cnt가 0이라 나보다 큰 애는 없어도 자리가 비워져있지 않다면 나보다 작은 친구가 들어간 곳이다. 다음 공간을 본다. cnt도 0이고 현재 공간이 0이면 내가 들어갈 자리이다. import java.util.Scanner; publi..
www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제자체는 어렵지 않은데 시간초과가 있어서 최적화해줘야한다. --- 풀이 r길이는 2인데 속도가 1000이라면 엄청나게 왔다갔다해야된다. 같은 위치에 있을 경우의 규칙을 찾아야된다. 주의할 점은 같은 위치에 있더라도 방향이 반대인 것은 같은 경우가 아니다! 예를 들면 C=5이고 현재 열 번호 1에 있고 우로 움직이는 상어가 있다고 하자 열 번호 1 2 3 4 5 인 경우 S=1이면 오른쪽으로..
www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 추가 설명에 비에 모두 잠기지 않을 가능성이 있다고 했다. (비가 안오는 경우가 있다. 높이 모두 1인 곳의 기준) 최대 지역의 높이 = 비의 최대 강수량으로 놓고 모든 비의 높이에 따라서 bfs를 돌려준다. 비의 높이보다 낮은 곳은 모두 0으로 만든 후 여전히 양수인 (물에 잠기지 않은 곳)의 영역을 구해준다. import java.util.LinkedList; import java.util.Queue; import..
www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net subset을 사용해서 처리해줬다. 길이가 1이상이라는 조건이 있다 import java.util.Scanner; public class Main { static int n,s; static int[] arr; static int answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in)..
www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 중간 중간에 조건들을 처리해줘야 할 것이 많다. 디버깅이 안되서 아예 다시 풀었다. 도착지, 출발지 정보를 다 저장하고 taxi클래스를 또 따로 만들어줬다. 한 사람의 도착지 = 다음 승객의 출발지이거나 초기 택시 출발지 = 이미 승객이 거기 서있음 의 경우로 택시 위치의 승객은 또 따로 처리해줘야 된다. 각 승객은 (출발지 != 도착지) 정보를 가졌지만 모든 승객이 같은..
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net subset으로 집합을 나눈다. vis[번호]=true => a집합, false면 b집합 만약 리스트 두 개를 만들어서 각각 집어넣는다. 리스트 하나라도 길이가 0이다 => 나머지 몰빵 => 집합 2개가 안됨 => return 리스트 두 개의 길이를 합쳤는데 n이 안됨 => 집합이 3개 이상이라는 뜻 => return 그 다음에는 한 집합 내에서 bfs로 인접리스트를 돌리며 한 집합의 모든 원소가 연결되는 지 확인한 후 두 집합 합..