목록2024/10/01 (1)
미소를뿌리는감자의 코딩
[백준 2024/10/01] 11049번 행렬 곱셈 순서
1. 문제https://www.acmicpc.net/problem/11049 2. 접근 방법https://www.youtube.com/watch?v=Tdl6VP4bS90 이 문제는 행렬의 계산 횟수를 구하는 문제이다. 위 영상이 이해에 큰 도움을 주었다.그림으로 설명하기 위해 아래 그려 보았다.(ABC)(DEFGH) 로 묶었다고 가정하였을 때, 계산 횟수는 z * c* h 가 된다. 즉, 이를 list를 이용해서 표현해 보면, row[x] * column[k] * column[y] 이다. 이후, 재귀적으로 ABC에 대해서, 그리고 (DEFGH)에 대해서 탐색해야 하므로이를 다시 dfs에 범위를 재설정하여 넣어준다. 탈출 조건은 x와 y가 같은 값을 지닐 때, 이다.또한 memoization을 사용해 주어..
코딩 테스트/백준
2024. 10. 1. 22:33