본문 바로가기

PS

BOJ #13907 세금 문제 링크 : https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 특정 정점을 방문하는 최단 경로를 구하는 문제이지만, 각 간선들의 통행료를 인상함에 따라 최단 경로가 변경될 수 있음에 유의해야 합니다. dist[i][j] :: 시작 정점으로부터 i번 정점에 도착하기까지 j개의 간선을 이용했을 때의 최소 비용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1.. 더보기
BOJ #1865 웜홀 문제 링크 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀 www.acmicpc.net 그래프의 경로 상에 음수 간선이 존재하는 벨만포드 알고리즘 입문 문제입니다. 별도의 트릭을 필요로 하지 않으며 벨만포드 알고리즘을 충실히 구현하면 됩니다. 벨만포드 알고리즘의 정의상, 정점의 개수(V) - 1회만큼 경로 갱신을 반복하면 전체 최단 경로들을 모두 구할 수 있습니다. 이후에 한번 더 인접 리스트를 통해 경로 갱신을 했을 때 최단 거리가 갱신되는 경우가 발생한다면, 해당.. 더보기
BOJ #1857 발레리노 문제 링크 : https://www.acmicpc.net/problem/1857 1857번: 발레리노 문제 김주성은 사실 뛰어난 발레 실력을 숨기고 있다. 그는 매일 밤 열심히 발레 연습을 한다. 그는 항상 연습하는 곳의 바닥을 m행 n열의 정사각형 칸들로 나누어 놓고 춤을 춘다. 그가 춤을 추�� www.acmicpc.net dist[x][y] :: 출발점에서 x,y 위치까지 이동하기 위해 사용한 방석의 개수 ans[x][y] :: 출발점에서 x,y 위치까지 이동하기 위해 방석을 배치하는 경우의 수 돌멩이가 없는 각 좌표들에서, DFS를 이용해 '현재 좌표에서 이동할 수 있는 좌표'들을 인접 리스트에 넣어 줍니다. 인접 리스트를 돌며, 아직 방문하지 않은 좌표라면 필요한 방석을 1개씩 더해주며 경로를 .. 더보기

티스토리툴바