글 읽기 - 모듈러 연산에 대해 질문드릴게 있습니다!

cocoon 3년 전 0

맨 아랫줄에

cout << sum[1].back() % MOD; 이부분을

cout << (sum[1].back() + MOD) % MOD; 으로 고쳐야 코드가 통과됩니다.

제가 생각하기로는 sum[1].back() 은 음수가 나오지 않기 때문에

sum[1].back() % MOD 랑 (sum[1].back() + MOD) % MOD 는 차이가 없다고 생각되는데

제가 놓치고 있는게 있는지 궁금해서 질문 드립니다!

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

#define MOD 1000000007

int N, LIS_len;
int A[1000001], dp[1000001], LIS[1000001];
vector<long long> num[1000001], sum[1000001];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	// 수열 입력받기
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];

	// LIS 길이 구하기
	for (int i = 0; i < N; i++)
	{
		int idx = lower_bound(LIS, LIS + LIS_len, A[i]) - LIS;
		LIS[idx] = A[i];
		dp[i] = idx + 1;
		LIS_len = max(LIS_len, dp[i]);
	}

	cout << LIS_len << " ";

	for (int i = 1; i <= LIS_len; i++)
		sum[i].push_back(0);

	for (int i = N - 1; i >= 0; i--)
	{
		int j = 1;
		int len = dp[i]; // LIS 길이

		if (len < LIS_len)
		{
			int idx = upper_bound(num[len + 1].begin(), num[len + 1].end(), A[i]) - num[len + 1].begin();
			j = sum[len + 1].back() - sum[len + 1][idx];
		}
		num[len].push_back(A[i]);
		sum[len].push_back((j + sum[len].back()) % MOD);
	}
	
	cout << sum[1].back() % MOD;

}

slah007 3년 전 1

채점할 때 sum[1].back>=0인지 assert()로 확인해 보세요. 제가 코드를 이해한건 아니지만 둘이 다른 경우는 음수인 경우밖에 없고 44번줄로 인해 음수가 나올수도 있을 것 같습니다.

sait2000 3년 전 1

...제 코드인가요 ???

44번 줄이 문제인 거 맞습니다. 저 부분합이 중간에 MOD값을 넘어가게 되면 논리적으로는 큰 거에서 작은 걸 빼는 거지만 계산한 값은 음수가 나올 수 있습니다. 그러면 47번 줄에서 다시 음수가 나올 수 있습니다.

가장 깔끔한 해결책은 44번 줄에다 + MOD % MOD를 하는 거라고 생각합니다.

cocoon 3년 전 0

감사합니다

문제가 어려워서 구글에 풀이법도 별로 없고해서 푸신분들 코드 보면서 가장 깔끔하신거같아서 참고했던것같습니다.

jh01love 8달 전 0

@sait2000

실례를 무릎쓰고 질문 하나만 드리겠습니다..

위 코드에서41~48번째 줄의 의미를 아무리 고민해봐도 잘 모르겠습니다.

저 과정을 수행하면 num과 sum이 나와 정답이 나온다는것은 이해하는데 왜 그런 아이디어가 쓰였는지 궁금합니다..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

모듈러 연산에 대해 질문드릴게 있습니다!

cocoon 3년 전 0

slah007 3년 전 1

sait2000 3년 전 1

cocoon 3년 전 0

jh01love 8달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말