전체 글
-
[백준 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을 더해서 배열에 저장..
-
[SWEA 3234 - 준환이의 양팔저울]Algorithm 2020. 11. 9. 18:27
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 준환이가 양팔 저울에 모든 무게추를 올리는 방법은 총 몇 가지가 있을까? 하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다. DFS를 이용하여 순열을 구현하는 문제다. 나는 올리는 과정에서도 오른쪽이 왼쪽보다 무게가 적어야 한다는 것을 생각하지 못해서 2번정도 fail했다. DP를 이용하지 않고 순열로 구현했기 때문에, StringBuilder와 매개 변수로 전달해주어야 시간 초과가 나지 않는다. 풀이 방법 dfs를 이용해서 순열을 구현한다. 아래 두가지 경..
-
[SWEA 4193 - JAVA] 수영대회 결승전Algorithm 2020. 11. 9. 18:25
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 삼성이를 우승시키기위한 최단 경로의 시간을 출력하자! 신호등 문제로 BFS에 현재시간과 소용돌이를 건널 수 있는 시간을 비교해서 큐에 넣어준다. 소용돌이의 시간이 일정하기 때문에 신호등이나 견우와직녀보다는 비교적 쉬운 문제다. 풀이 방법 시작점을 큐에 넣어준다. 큐 사이즈를 받아서 사이즈 만큼 돌아준다 (시간 체크) 소용돌이를 만날 경우 건널 수 없으면 다시 큐에 넣어준다. 2번을 체크해서 BFS를 구현할 경우 visit배열을 int형으로 해줄 필요가 없다 (메모이제이션 불필요) import java.io.*; import java.util.*; public cl..