[BOJ 1553] 길의 개수 "컷"
2022. 11. 10. 16:55ㆍPS/Problem Solving
https://www.acmicpc.net/problem/1533
http://boj.kr/42cd430fb1f94613bdc6b6d2feb6a7fd
인접행렬 거듭제곱이라는 개념을 사용해야 하는건 본대 산책 시리즈를 풀어봤으면 바로 보인다.
다만 길에 가중치가 있어 이를 적절히 1짜리 길로 나누어줘야 하는데, 각 길마다 정점을 새로 만들어주면 N = 10*10*5 = 500으로 행렬 곱셈을 할 때 시간이 너무 많이 걸린다. 따라서 각 정점마다 4개의 새로운 정점을 추가하는 방식으로 해결할 수 있다.
앞으로 바로 못 푼 문제나 신기한 아이디어를 사용하는 문제는 복습용 문제집에 저장해둔다.
728x90
'PS > Problem Solving' 카테고리의 다른 글
[BOJ 3015] 오아시스 재결합 "컷" (2) | 2022.11.13 |
---|---|
[BOJ 2533] 사회망 서비스(SNS) "컷" (1) | 2022.11.12 |
[BOJ 1006] 습격자 초라기 "컷" (1) | 2022.11.07 |
VS Code C/C++/Python 설정 방법 - PS를 위한 (3) | 2022.10.22 |
0901 금토일 연습 (0) | 2022.09.04 |