전체 글

BOJ - 괄호 추가하기 16637번 (JAVA)

❓ 문제 - 백준 괄호 추가하기 16637번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/16637) 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 📝 문제해결법 1. 이 문제는 DFS(백트래킹)으로 구현하였다. DFS 내에서는 괄호를 안치고 계산한 경우와, 괄호를 치고 경우 이렇게 두 개를 가지치기를 하면서 푼다. 예를 들어 3+8*7-9*2 에서 3+8*7 ~~ 로 오른쪽에 괄호를 안 치고 계산하는 경우 3+(8*7) ~~ 로 오른쪽에 괄호를 치고 계..

BOJ - 녹색 옷 입은 애가 젤다지? 4485번 (JAVA)

❓ 문제 - 백준 녹색 옷 입은 애가 젤다지? 4485번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/4485) 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 📝 문제해결법 1. 이 문제는 다익스트라 풀이로 해결하였다. 일단 N이 125라서 DFS, BFS로 완전탐색 나오면 시간초과 발생함 -> 다익스트라로 풀어야함 어차피 출발지(0, 0)에서 목적지(n-1, n-1)의 최단 거리를 구하는 문제로 해석되기 때문에 다익스트라로 풂 링크는 인접한 4방향(..

BOJ - 서강그라운드 14938번 (JAVA)

❓ 문제 - 백준 서강그라운드 14938번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/14938) 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 📝 문제해결법 1. 이 문제는 다익스트라 풀이로 해결하였다. 우선순위 큐를 활용한 다익스트라 방법을 사용하여 모든 지역마다 시작점을 두고 최단 거리를 계산해준다. 그리고 계산해준 거리를 통해 만약 갈 수 있는 지역이고, 그 거리가 m이하라면 해당 지역의 아이템 수를 sum에 더해주고 계산이 끝난 sum을 최대값과 비교해서 갱신해줘 ..

BOJ - 주사위 굴리기2 23288번 (JAVA)

❓ 문제 - 백준 주사위 굴리기2 23288번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/23288) 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 📝 문제해결법 1. 이 문제는 시뮬레이션 + BFS 으로 문제를 풀었다. K번의 주사위를 굴릴 때 현재 방향으로 이동한 뒤 점수 계산을 위해 그 이동한 곳에 위치에 있는 점수와 같은 점수가 몇 개 인접했는지 카운트 하는 것을 BFS로 구현하였다. 전체 구현 흐름은 다음과 같다. 주사위의 방향으로 이동해보고..