본문 바로가기

Algorithm

 (117)
[백준] JAVA - 16918. 봄버맨 https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 생각 처음엔 나머지 연산을 해서 폭탄위치 마킹 -> 빈곳에 폭탄 채우기 -> 폭탄위치가 마킹된곳 BFS로 폭발시키기 이런식으로 구현했는데 주기별로 위의 상태가 변화하는것이 아니라서 문제에서 요구하는것을 그대로 구현하도록 했습니다. 1. 폭탄이 설치된 위치를 큐에 넣어줍니다. (초기상태, 1초 후) 2. 빈곳에 폭탄을 채워넣습니다. 3. 1초 증가시켜줍니다. 만약 time이 주어진 N초와 같다면 리턴합니다. 4. b..
[백준] JAVA - 17143. 낚시왕 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 생각 단순하게 1초마다 상어를 움직이는 방식으로하면 시간초과가 난다고 알고있었는데 스터디원이 통과가됐다고 해서 저도 이렇게 바꿔서 제출했더니 통과했습니다.. 원래는 아래와 같은 방법으로 상어의 위치를 계산하도록 했는데 계속 틀렸다고 나왔습니다 어느 부분이 문제인지를 모르겠네요 ㅠㅡㅠ (추가) 나머지 연산을 사용하여 다시 풀었습니다! 상어가 다시 제자리로 위치하기 까지 2*(크기..
[백준] JAVA - 1577. 도로의개수 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 100보다 작거나 같은 www.acmicpc.net 생각 스터디원의 도움을 받아 풀었습니다!!! (따봉우재야 고마워~) 0. dp의 값이 int의 범위를 벗어나므로 타입을 long으로 해줘야합니다!!! (int로 하면 틀렸다고 나옵니다ㅠㅠ 범위 체크를 꼭 해주자.. 메모메모) 1. 우선 맵을 반대로 뒤집어서 좌표의 출발점을 (0,0) 도착점을 (N,M)으로 잡아줍니다. 2. 이때 이동할수있는 방향은 두가지로 왼쪽->오른쪽, 위->아래..
[백준] JAVA - 1194. 달이 차오른다,가자. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 생각 BFS + 3차원 상태 배열 + 비트마스킹을 모두 생각해야하는 문제였습니다 ㅜㅜ ( 비트마스킹을 통해 상태를 표현하는게 더 쉬운 문제 : 백준 15683 감시 hyewon-study-log.tistory.com/106?category=976036 ) [백준] JAVA - 15683. 감시 https://www.acmicpc.net/problem/15683 156..
[백준] JAVA - 1647. 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 생각 마을을 두개로 분리해야하고 분리된 마을들은 내부에서 서로 모두 연결되어있어야 합니다. 또한 분리된 마을들은 최소의 비용으로 서로 모두 연결되어있어야 합니다. 즉, 그래프에서 최소 비용을 찾는 문제로 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리인 MST(최소 신장 트리)를 구성해야 합니다. 이를 만족하기 위해서 아래의 작업을 수행해줍니다...
[백준] JAVA - 15683. 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 생각 'SWEA 1767. 프로세서 연결하기'와 로직이 비슷하다고 생각했습니다. CCTV가 탐색할수있는 영역을 모두 탐색하여 CCTV를 켜준 곳을 9로 마스킹처리를 해줬습니다. 그 다음 CCTV를 다시 0 값을 넣어 꺼줬다고 생각했는데 CCTV가 탐색하는 영역이 겹칠 수 있기 때문에 이렇게 바로 값을 특정 값으로 업데이트 시켜줘서 계속 틀렸습니다ㅠㅡㅠ 1. 비트 마스킹으로 CCTV의 방..
[백준] JAVA - 20056. 마법사 상어와 파이어볼 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 생각 같은좌표에 있는 파이어볼을 나눠줄때 혼자 있는 파이어볼을 고려하지 않고 헤메다가 두번째 시도만에 풀었습니다..!! - 큐를 사용하여 각 단계별로 파이어볼의 이동을 동시에 처리해줬습니다. - 파이어볼 클래스를 생성하여 파이어볼 이동함수와 합치는 함수를 내부에서 따로 구현해줬습니다. move 함수는 파이어볼이 다음에 움직일 좌표를 계산합니다. 이때 '1번 ..
[백준] JAVA - 2629. 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 생각 시간초과로 친구의 도움을 받아 문제를 해결했습니다ㅠㅠ 완전탐색을 해버리면 부분집합인 O(2^N)의 시간복잡도를 가지게 되고 구슬의 개수가 M개이니 총 O(M*2^N) 을 가지게 됩니다. 따라서 dp와 메모이제이션을 통해 문제를 풀어야 합니다. 양팔 저울에서 왼쪽에 구슬을 위치시키고 오른쪽에 추를 위치시켜서 무게를 찾는다고 생각합니다. 다음으로 dp[i][j] : i번까지 추를 확인했을때 무게 ..

티스토리툴바