본문 바로가기

188581

[BOJ] 18858 : 훈련소로 가는 날 문제 링크 https://www.acmicpc.net/problem/18858 18858번: 훈련소로 가는 날 1 이상 M 이하의 정수로 이루어진 길이 N의 수열 중 논산인 것의 개수를 998,244,353으로 나눈 나머지를 출력한다. www.acmicpc.net 논산(Non-산)인 수열이 몇 개인지 출력하는 문제. 풀이 논산이란 Non-산 즉 산이 아닌 수열을 의미한다. a1 a3 처럼 올라갔다 내려가는 형태의 수열을 산이라고 부르기로 한다. 여기서 DP배열을 어떻게 선언할지가 관건인데, 수열의 i번째 수에 대해서 3가지의 경우로 나누어서 생각할 수 있다. 1. i-1번째 수와 비교했을 때 i번째 수가 더 큰 경우. 즉, 올라온 경우(오르막) 2. i-1번째 수와 비교했을 때 i번째 수가 .. 2022. 4. 6.

이전 1 다음

티스토리툴바