https://www.acmicpc.net/group/practice/view/543/277
팩토리얼을 계산하는데, 결과의 마지막 자리만 반환하는 문제다. 예를 들어 6!이면 6!의 마지막 자리만 반환하는 것이다.
팩토리얼을 계산하면서 곱할 때마다 결과를 10으로 나눈 나머지를 취하면 최종적으로 마지막 자리가 된다.
int solve(int n) {
int result = n % 10;
for(int i = n - 1; i >= 1; i--) {
result = (result * i) % 10;
}
return result;
~~~~}
숫자로 구성된 문자열(1 ≤ 길이N ≤ 10^6)이 주어질 때, 부분 문자열 ‘2’는 1점을, ‘22’는 2점을 ‘22…2’는 문자열의 개수 K만큼 더하는 프로그램을 작성하는 문제다. 부분 문자열은 서로 겹칠 수 있다. 예를들어 22222 라면 2, 22, 222, 2222, 22222 를 모두 고려해야한다.
처음에는 범위가 int를 넘어간다는 사실을 몰라서 오답처리를 받았다.
ll solve1(string& s) {
ll count = 0;
ll result = 0;
s.push_back('0');
for(int i=0;i<=N;i++) {
if(s[i] == '2') {
++count;
continue;
}
// 이 부분을 줄일 수 있다.
for(int j=1;j<=count;++j) {
result += (count - j + 1) * j; // 나타나는 개수 * 길이
}
count = 0;
}
return result;
}
여기서 줄일 수 있는 부분이 있는데 바로 수학을 이용하는 것이다.
결론부터 말하면 count(count+1)(count+2)/6 으로 저 반복문을 대체할 수 있다.
ll solve1(string& s) {
ll count = 0;
ll result = 0;
s.push_back('0');
for(int i=0;i<=N;i++) {
if(s[i] == '2') {
++count;
continue;
}
result += count * (count+1) * (count+2) / 6;
count = 0;
}
return result;
}