코딩무식자 전공생

문제출처: https://www.acmicpc.net/problem/1834

문제

N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.

입력

첫째 줄에 2,000,000 이하의 자연수 N이 주어진다.

출력

첫 줄에 구하고자 하는 수를 출력한다.

풀이

간단해 보이는데 정답률이 낮은문제입니다.제 생각에 수학문제나 dp문제나 메모이제이션의 유무만 다르지 둘 다 규칙찾기문제같습니다.

답이될수 있는 자연수의 범위가 주어지지않았기 때문에 단순히 반복문for(int i=1; i<=200000;i++) 내부에서 1부터 i/n==i%3)인 수를 찾아서 더해가는 풀이는 답이될 수없습니다.  애초에 답이될수 있는 자연수의 범위는 1~200000도 아닙니다. 그럼 규칙을 찾아봅시다.

n=1일때 -> 없음

n=2일때 3

n=3일때 4, 8

n=4일때 5,10,15

n=5일때 6,12,18,24

보이시나요? 여기서 확실하게 알아야될 건 n=4,n=5일때 끝값이 15,24라는 겁니다. 규칙대로 각각 20,30은될 수 없습니다.

n=3일때 나머지로 나올 수잇는 수는 1,2,0으로 3가지인데, 0은 나눠서 나올 수가 없기 때문에 무조건 n-1가지밖에 없습니다.  마찬가지로 n=4일때 나머지는 0,1,2,3이 나올 수 있는데 0은 셈하지않으니 3번연산합니다. 마지막으로 입력값이 최대 20만이라 ans는 int형 범위를 초과할 수 있으므로 longlong 형으로 선언해주면됩니다. 이 것을 코드로 작성하면 끝입니다. 

코드

#include<iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	if (n == 0 || n == 1)
	{
		cout << 0 << endl; return 0;
	}
	long long ans = 0;
	for (int i = 2; i <= n; i++)
	{
		ans += (long long)(n + 1) * i;
	}
	cout << ans;
}

결과

문제출처: https://www.acmicpc.net/problem/1964

문제

오각형의 각 변에 아래 그림과 같이 점을 찍어 나간다. N단계에서 점의 개수는 모두 몇 개일까?

입력

첫째 줄에 N(1≤N≤10,000,000)이 주어진다.

출력

첫째 줄에 N단계에서 점의 개수를 45678로 나눈 나머지를 출력한다.

풀이 

규칙찾기문제입니다. 규칙을 찾아볼까요? 1단계는 5, 2단계는 12, 3단계는 22, 4단계는 35...... 여기서 각 단계는 전 단계 + @이므로 식을 다시 써보면,

1단계->5, 2단계-> 5+7, 3단계->5+7+10, 4단계->5+7+10+13.... 규칙이보이사나요? 맞습니다. 2단계부터 7을 시작으로 3씩 증가하는 등차수열입니다.

식을 그대로 코드로 작성하면됩니다. 주의할건 입력의범위가 크므로 ans를 longlong으로 선언해주는겁니다. 

그리고 dp가 메모리를 많이잡아먹는다는것을 보이기위해 아래에 dp로 푼 실행결과도 올렸습니다.

코드

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	long long ans = 5;
	long long num = 7;
	for (int i = 2; i <= n; i++)
	{
		ans += num;
		num += 3;
		ans = ans % 45678;
	}
	cout << ans << endl;
}

결과

dp

반복문

문제출처: https://www.acmicpc.net/problem/1748

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤100,000,000)이 주어진다.

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

풀이

노트에 규칙성을 찾기위해 각 자릿수의 수들의합은 몇자리인지 적어봅니다

(1~9는 9, 10~99는 180,100~999는 2700입니다. 보기의 120의 답은 252입니다. 규칙성을 눈치채셨나요?

답은 n-1자리수까지의 숫자들을 나열한 수의 자릿수 + (n(끝값) - n자릿수의 시작 수- +1) * n입니다.

( 120-> 9(1~9) +180(10~99) + 63(100~120)=252 )

좀 복잡해보이지만 코드를 보면 이해가 갈거에요.

결론적으로, 위의 수식에서 색칠된 부분만 변수로 선언하여 답을 유도하면됩니다.

코드

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string n;
	cin >> n;
	//120의 자릿수=3
	int len = n.size();
	//1~9자릿수 합=9
	//10~99자릿수 합180
	//100~120자릿수 합 63
	//답: len-1자릿수까지의합+(n-n자리숫자의시작수+1)*n의 자릿수
	if (len == 1)
	{
		cout << stoi(n);
		return 0;
	}
	//temp1=n자리숫자일때끝값(1자리:9,2자리:99,3자리:999)
	//temp2=n자리숫자일때첫값(1자리:1,2자리:10,3자리:100)
	int ans = 0, temp1 = 9, temp2 = 1;
	for (int i = 1; i < len; i++)
	{
		ans += temp1 * i;
		temp1 *= 10;
		temp2 *= 10;
	}
	cout << ans + (stoi(n) - temp2 + 1) * len << endl;

}

결과

문제출처: https://www.acmicpc.net/problem/5691

문제

세 정수 A, B, C의 평균은 (A+B+C)/3이다. 세 정수의 중앙값은 수의 크기가 증가하는 순서로 정렬했을 때, 가운데 있는 값이다.

두 정수 A와 B가 주어진다. 이때, A, B, C의 평균과 중앙값을 같게 만드는 가장 작은 정수 C를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, A와 B가 주어진다. (1 ≤ A ≤ B ≤ 109) 입력의 마지막 줄에는 0이 두 개 주어진다. 

출력

각 테스트 케이스에 대한 정답을 한 줄에 하나씩 출력한다.

풀이

단순히 세 수의 평균값과 중앙값을 같게 만드는 수를 구하는문제입니다.

정답률을 보고 대충 주어진 입력 케이스를 유추하여 '2A-b인게 답이구나'  생각 할 수있지만 노트에 끄적여보며 왜 저 식이 답인지 알아봅시다. 이런 손으로 푸는 연습들이 어려운 수학문제를 풀 때 충분한 밑거름이 될 거라고 생각합니다.

1. 세 수의 평균을 구하는 식은 (A+B+C)/3입니다.(이 때 C가 답)

2. C를 추가했을 때 가장 작은 중앙값은 무조건 A입니다. (A의 왼쪽에 오나 오른쪽에 오나 가장 작은 중앙값은 A이므로)

3. 구하는 답이 1번식==2번식일 때 C의 값이므로 풀어써봅니다. 나오는 C에대한 식을 출력하면됩니다.

(A+B+C)/3 == A   -> (A+B+C)==3A   -> C=2A-B 

코드

#include<iostream>
using namespace std;
int main()
{
	int a, b;
	while (1)
	{
		cin >> a >> b;
		if (a == 0 && b == 0)
			break;
		cout << 2 * a - b << endl;
	}
}

결과