백준
-
[백준 - JAVA] 치킨 배달Algorithm 2020. 12. 9. 17:37
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제를 풀기 시작하자마자 치킨이 먹고 싶어져서, 스터디원들과 30분만에 풀고 다같이 치맥을 먹으러 갔던 문제 ◝(⁰▿⁰)◜ M이 13이하의 수이기 때문에 기초적인 조합을 구현할 수 있다면 풀 수 있다! 풀이 방법 입력을 받으면서, 치킨집과 집의 좌표를 리스트에 각각 저장한다. 치킨집의 리스트로 dfs를 이용한 조합을 구현한다. boolean형 배열을 이용해서 중복 처리를 한다. 치킨집을 M개 골랐을 때 도시의 치킨거리를 구한다. M개의 치킨집..
-
[백준 3109 - JAVA] 빵집Algorithm 2020. 11. 26. 11:40
3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 스터디 과제로 나왔지만, 예전에 풀었던 문제라서 코드를 보면서 복기만 해봤다. dfs를 이용했고, 모든 시작점에서 출발하여 파이프를 연결할 수 있을 경우 계속 진행하는 백트래킹 방식으로 풀었다. 풀이 방법 행의 수 만큼 dfs를 시작한다. 오른쪽위, 오른쪽, 오른쪽 아래로 이동하며 범위안이며 건물이 아닐 경우에만 dfs를 진행한다. 열의 끝에 도달한 경우 ans를 증가시킨다. import java.io.*; import java.util.*; public class Main {..
-
[백준 13459 - JAVA] 구슬 탈출Algorithm 2020. 11. 17. 18:20
13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 보드를 기울이면 구슬이 끝까지 이동하는데, 구슬이 겹치는 상황에서 어떤 구슬이 앞쪽에 있는지만 신경쓰면 크게 어렵지 않은 문제! 풀이 방법 빨간 구슬의 위치와 파란 구슬의 위치를 갖고 있는 클래스를 구현한다. (1차원 배열로 해도 될것 같다.) 네 방향으로 기울여서 이동한 위치를 확인한다. move 메소드에서 처음 빨간 구슬의 위치가 앞인지 먼저 체크를 해준다. 빨간 구슬과 파란 구슬을 벽이 나올때까지 혹은 구멍에 ..
-
[백준 11062 - JAVA] 카드 게임Algorithm 2020. 11. 12. 18:32
11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 정말정말 DP는 풀 때마다 모르겠다! 결국 블로그를 참고해서 어떻게 푸는지 보고 풀었다. 최선의 전략으로 진행하는 것이기 때문에 모든 경우를 확인해야하고, DP를 이용해 각 턴마다 근우가 높은 점수를 얻는 경우와 명우가 낮은 점수를 얻는 경우를 저장해둔다. 그래서 DP배열은 [근우와 명우의 턴][시작 카드(왼쪽 끝)의 인덱스][마지막 카드(오른쪽 끝)의 인덱스]로 크기는 [2][N][N]으로 할당한다! 풀이 방법 DP배열의 초기값을 -1로 넣어준다. 턴은 근우부터 0..
-
[백준 4386 - JAVA] 별자리 만들기Algorithm 2020. 11. 12. 17:52
4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 기본적인 MST (최소스패닝트리) 문제! 나는 입력을 잘 못 받아두고 왜 안되냐고 고통받다가 나중에 발견했다 :( 프림이나 크루스칼 둘 중에 한가지를 사용해서 풀 수 있는데, 나는 프림을 사용해서 풀었다. 크루스칼은 union, findSet을 구현하기가 너무 귀찮았다 =(:з」∠)_ 풀이 방법 입력받은 좌표를 이용해 다른 별과의 거리를 구한다. 첫번째 별부터 시작! 다른 별들의 번호와 첫번째별과의 거리를 Edge 객체로 만들어 PQ에 넣는다. 방문한 별의 개수(..
-
[백준 1937 - JAVA] 욕심쟁이판다Algorithm 2020. 11. 9. 19:28
1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 현재 장소보다 대나무가 많은 지역으로만 이동할 수 있는 판다가 가장 오래 살아남는 기간을 구하는 문제! 단순하게 dfs로 풀었다가 시간초과를 받았다. DP라고해서 고민을 하다가 결국 블로그를 참조했다. 기간을 정해서 DP문제를 집중적으로 푸는 시간을 가져야 할 것 같다... ŏ̥̥̥̥םŏ̥̥̥̥ 풀이 방법 dfs를 통해 끝에 도달했을 때 그곳의 cnt(살아남은 날짜)는 1이 된다. * 더 이상 이동하지 못하기 때문에 그곳에서는 하루만 살 수 있다. 그리..
-
[백준 1261 - JAVA] 알고스팟Algorithm 2020. 11. 9. 19:13
1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 방향을 맞게 잡았으나 조건을 잘못 넣어서 메모리 초과가 2번 났었다. 다익스트라인줄 몰랐으나 풀고보니 최소 횟수를 따라가며 갱신할 수 있을 때 큐에 삽입하는 다익스트라 방식으로 잘 풀었었다ㅎㅎ... 풀이 방법 벽을 뚫은 횟수(이하 cnt)를 저장할 2차원 배열(ans) 을 생성하고 큰값으로 초기화한다. 초기 장소인 0, 0 cnt는 0으로 배열을 만들어 cnt가 기준인 우선순위큐에 넣는다. * 처음 장소는 항상 뚫려있다. 큐가 빌때까지..
-
[백준 3108 - JAVA] 로고Algorithm 2020. 11. 9. 18:28
3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다! 이삭이가 BFS를 이용해서 컬러링을 해보려했다는 것에서 아이디어를 얻어 풀었던 문제다. 일반적인 BFS로 풀경우 하나의 직사각형안에 겹치지 않게 딱맞게 직사각형이 들어갈 경우 겹친다고 체크하는 문제가 발생한다. 나는 직사각형을 그리면서 겹칠 경우 FindSet을 이용해 집합을 확인하고, 같은 집합이 아닐 경우 ans에서 1을 빼주도록 구현했다. 가운데 영점이 존재하는 좌표계이기 때문에 500을 더해서 배열에 저장..