전체 글

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 풀이 풀이 방식은 이전 포스팅과 동일하다. https://katastrophe.tistory.com/19 [BOJ] 백준 [1753] 최단경로 JAVA https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 문제 풀이 nlogn 시간복잡도인 우선순위큐를 이용한 다익스트라 기본 풀이다. 간선의 가중치 낮은 순으로 우선순위큐에 들어가기때문에 n^2 방식인 최소비용탐색하는 시간이 들지 않기때문 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 ..

https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제 풀이 아 .. 비트마스킹이란걸 몰라서 한참을 헤매었다.. 결론적으로는 열쇠의 유무를 2^6 = 64 , 즉 visit배열을 3차원으로 열쇠유무까지 추가하면 => visit[높이][너비][열쇠] visit[h][w][64] 이렇게 두고 풀어야 한다는 것이다. 열쇠면 | 연산으로 추가 , 문 이면 & 연산으로 확인하는 식으로해서 탐색을 하면 된다. 1 2 3 4 5..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 풀이 단순 DFS 시뮬레이션 문제이다. 특이한점은 dfs 안의 다른 조건으로 재귀호출을 두 번 한다는것. map[y][x] = 1 : 벽 map[y][x] = 2 : 청소 된 상태로 만들기 map[y][x] = 0 : 청소 안된 상태 문제에 나와있는 조건을 따라서 탐색한 방향 nextX,nextY 가 청소되어있는지 확인 후 움직이거나 청소가 다 되어 있거나 벽인경우 , 후진 할 수 있다면 ..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 풀이 처음에 PriorityQueue를 쓰다가 33%쯤에서 틀렸다고 나왔다. 힙 구조특성상 맨 앞에있는 원소만 순서를 보장해줘서 그런 것 같다. 결론은 LinkedList 큐 에서 하나 뽑은 다음 , 더 높은 중요도의 문서가 있다면 그냥 큐의 뒤로 보내는 것이 가장 정석적인 방법일 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23..

https://www.acmicpc.net/problem/16197 문제 풀이 이 문제에서 내가 집은 포인트는 3 가지이다. 1. 동전 위치를 나타내는 Point 객체와 두 동전을 담고 움직이는 횟수를 나타내는 Move 객체를 생성 2. 우선순위큐를 이용하여 횟수가 적은 순서대로 처리 3. isRange(x,y) 로 범위를 벗어나는 조건을 이용해서 둘 중 하나만 떨어지는 경우를 체크 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64..

https://www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net 문제 풀이 이 문제에서 내가 집은 포인트는 3 가지이다. 1. 우선 순위 큐를 이용하여 최대한 시간이 덜 걸리는 순으로 처리하는 것 (우선순위큐 bfs 다익스트라 이용) 2. dp배열을 이용해서 이미 왔던 곳이면 break를 거는 것 3. 이중 for 문을 이용해서 nextX,nextY를 정할 때 , 1부터~k까지 이동가능한 모든 경우를 큐에 넣는 것 1 2 3 4 5 6 7 8 9 1..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 풀이 전형적인 dp문제이다. 우선 단순 노가다로 풀어보다가 3번쨰마다 규칙이 있을거라는 추측을해본다. 두번째마다 1씩 올라가는 걸 확인 할 수 있다. 이걸 점화식으로 세우면 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.*; imp..