백준/DP
[코딩테스트] 백준 11660번: 구간 합 구하기 5
ydin
2022. 1. 10. 12:07
-문제: https://www.acmicpc.net/problem/11660
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
-정답 풀이1:
- 1~2번 라인 입력 해줘야 시간초과 발생하지 않는다
- dp인덱스는 i,j 모두 +1씩 해줘야 계산하기 편함
-정답 풀이2:
-틀린풀이:
- 간단하게 for문 두개로 풀려고 했는데 이게 O(n^2)라서 시간초과가 발생한다
-문제풀이 원리는 https://claude-u.tistory.com/427 여기를 참고했다.