사실 코테만 통과 하는게 목적이라

백준 플래 4 찍고 구현력 올리려고 요즘은 프로그래머스 푸는중이다가


scpc 신청 마지막날 그냥 연습삼아 참가 신청 했는데

1번 3번 2솔하고

2번문제 10점밖에 못 긁었는데 제출 횟수 다 써서 못품 ㅜ


근데 2번 푸는 방법 아이디어 자체는 틀린거 같지않은데 어떤지 한번 봐주삼

누적합 + map을 사용한 dp로 계속 맞왜틀 하다 10번 다 썼는데 아이디어 자체가 틀렸나해서 풀어서 써봄


입력을 받고 그것의 누적 합을 구함 (인덱스 1 부터 시작한다 가정)


그럼 n개의 합은 a[n]이니까 a[n] % k != 0 이면 방법은 0가지이니 a[n] % k == 0일때만 확인해서


g = a[n] / k 로 둔다면

누적합 a[i] 가 g 일때와 아닐때로 나눠서


a[i] == g일때는

m[a[i]] = (1 + m[a[i] - g] + m[a[i]]) % MOD;


아닐때는

m[a[i]] = (m[a[i] - g] + m[a[i]]) % MOD;


m은 map

i의 범위 (1 <= i < n) 에서 반복문돌리고



반복문끝나면 Answer = m[a[n] - g] 했는데 아예 방법이 틀린건가?


세그먼트 트리는 어차피 모르는데 혹시 그건가 싶다가고

누적합 + dp로도 충분히 풀수 있는 문제 같아보였거든


아 참고로 모든 int 자료형은 long long int 형으로 바꿔서 사용했음