코딩무식자 전공생

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

풀이

주어진 예제 케이스를 보면, 3개의 수를 정렬 시킨 뒤, 인접한 수의 차를 구한 뒤 그 수들의 최대공약수의 공약수가 정답임을 알 수 있습니다.

이를 검증해 보기 위해 몇가지 테스트 케이스를 만들어서 확인해보았습니다.

1) 8, 14, 17 

 -> 인접한 수의 차 : 6, 3

 -> 최대 공약수: 3

 -> 최대 공약수의 공약수: 3(정답)

2) 8, 12, 22

 -> 인접한 수의 차: 4, 10

 -> 최대 공약수: 2

 -> 최대 공약수의 공약수: 2(정답)

3) 17, 35 ,50 

 -> 인접한 수의 차: 18, 15

 -> 최대 공약수: 3

 -> 최대 공약수의 공약수: 3(정답)

4개, 5개의 숫자의 경우에도 확인해 보았는데 모두 맞았습니다. 따라서 아래의 순서대로 풀이를 진행하면 됩니다. 

1. 입력된 숫자들을 정렬하기

2. 인접한 숫자들끼리의 차를 구한 뒤 그 숫자들의 최대 공약수 구하기 ( 유클리드 호제법 이용)

3. 최대 공약수의 공약수 구하기

주의할 점은 3번 과정 중 반복문의 조건 에서 i의 범위를 주의해야합니다. 수의 최댓값이 10억이므로 계산과정에 따라 시간초과가 날 수 있습니다.

따라서 i의 범위를 줄여서 중복되는 계산 과정을 생략 할 수 있도록 합니다.

코드

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

풀이

그냥 단순히 3또는 7의 배수인 수를 구해서 정답을 구하면 100%시간초과가 뜹니다.

테스트케이스가 최대 10만번인데 입력범위가 최대 8만 까지이므로

T가 10만이고 모든 테스트케이스의 N이 8만인 최악의 경우 최대 80억번 연산을 해야합니다.

따라서 저는 연산 전 미리 10만까지의 수에 대해 배열에 그 값까지의 합을 구해놓고 풀었습니다.

예를들어 N이 49면 temp[49]는 3부터 49까지의 수 중 3또는 7의 배수일 때 그 수들의 합을 미리 저장해서 답만 출력시키게끔 했습니다.

이렇게 하면 최대 연산횟수를 80억번에서 18만번으로 떡락시킬 수 있습니다.

코드

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

풀이

피보나치 수열+ 규칙찾기 문제입니다.

시작인덱스를 0으로 잡으면 N번째 수는 arr[n-1]이고, 이 것을 이용해 둘레를 구해보면

n번째 수*2+ (n번째 수+n-1번째 수)*2가 됩니다.

코드

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

풀이

nCr == n-1Cr + n-1Cr-1로 표현할 수 있고 아래 내용들만 알고있으면 쉽게 dp 2차원배열로 풀수 있습니다.

1. r이 1이면 n에 상관없이 무조건 n 

2. n==r이면 무조건 1

3. r이 0이면 무조건 1

2중for문에서 i가 3, j=2부터 시작되는 이유는

i가 3보다 작을 때는 위의 3가지 조건들을 미리 계산해놓으면 아래 식 까지 계산되어서 굳이 또 계산할 필요가 없기 때문입니다.

1 1

2 1

2 2

3 1

코드

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

풀이

백트래킹으로 분류된 문제지만 이렇게풀어도될 것 같은데? 해보니 풀린 문제입니다. 

문자열 S를 앞에서부터 10의 제곱꼴로 저장해놓고 9,8,7,6...순으로 곱하면서 최댓값을 구할 수 있습니다. 아래에 문제 풀이 순서대로 적어보았습니다.

1. int형 알파벳 배열 선언하기

알파벳 갯수를체크하기위함이 아닌 입력받은S의 첫번째 알파벳부터 10의 제곱꼴로 하여 저장하기위해 선언. n번 만큼 반복해서 값을 누적시킵니다.

2. 최댓값을 구하기위해 알파벳 배열에 담긴 값들을 큰값부터 정렬시키기

3. 정렬시킨 알파벳배열의 값들이 최댓값 순으로 정렬되어있으므로 각 값들을 9,8,7,6...순으로 곱해나가기. 결국 최종sum이 최댓값이 되어있음

코드

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

행렬의 곱셈을 이용하여 분할정복 기법으로 푸는 문제입니다.

아래 링크에서 행렬곱셈을 이용한 접근방법에대해 공부하시고 풀 것을추천드립니다.

https://jow1025.tistory.com/101

풀이

입력값이 0일 때 0이출력되게끔만 해주면되고, 범위가 크기때문에 행렬을 담는변수, 입력 변수를 long long 형으로 선언해야합니다.

풀이는 행렬곱셈만할줄 알면되므로 생략하겠습니다.

코드

#include<iostream>
struct M
{
	long long data[2][2];
};
using namespace std;
long long fibo(long long x);
M divide(M a, long long x);
M multiply(M a, M b);
int main()
{
	long long n;
	cin >> n;
	if (n == 0) { cout << 0 << endl; return 0; }
	cout << fibo(n) << endl;
}
long long fibo(long long x)
{

	M a;
	a.data[0][0] = 1; a.data[0][1] = 1;
	a.data[1][0] = 1; a.data[1][1] = 0;
	a = divide(a, x);
	return a.data[0][1];
}
M divide(M a, long long  x)
{
	if (x > 1)
	{
		a = divide(a, x / 2);
		a = multiply(a, a);
		if (x % 2 == 1)
		{
			M b;
			b.data[0][0] = 1; b.data[0][1] = 1;
			b.data[1][0] = 1; b.data[1][1] = 0;
			a = multiply(a, b);
		}
	}
	return a;
}
M multiply(M a, M b)
{
	M c;
	c.data[0][0] = (a.data[0][0] * b.data[0][0] + a.data[0][1] * b.data[1][0])%1000000007;
	c.data[0][1] = (a.data[0][0] * b.data[0][1] + a.data[0][1] * b.data[1][1]) % 1000000007;
	c.data[1][0] = (a.data[1][0] * b.data[0][0] + a.data[1][1] * b.data[1][0]) % 1000000007;
	c.data[1][1] = (a.data[1][0] * b.data[0][1] + a.data[1][1] * b.data[1][1]) % 1000000007;
	return c;

}

결과

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

풀이

https://jow1025.tistory.com/35에도 나와있듯이, 삼각형의 성립조건은 세 변 a,b,c중 c가 가장 큰 변일 때 a+b>c일때입니다.

a+b>c일때 a,b,c의 합의 최댓값은 빨대의길이를 정렬하고 뒤에서부터(큰값부터)비교하면 됩니다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int straw[1000001];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> straw[i];
	sort(straw + 1, straw + n + 1);
	//c가 가장 큰 변일 떄 a+b>c일떄 삼각형성립
	for (int i = n; i >= 2; i--)
	{
		int c = straw[i];
		int a = straw[i - 1];
		int b = straw[i - 2];
		if (a + b > c)
		{
			cout << a + b + c << '\n';
			return 0;
		}
	}
	cout << -1 << '\n';
}

결과

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

문제

두 정수 A와 B가 주어졌을 때, 두 정수 사이에 있는 수의 합을 구하는 프로그램을 작성하시오. 사이에 있는 수들은 A와 B도 포함한다.

입력

첫째 줄에 두 정수 A, B가 주어진다. (-2,147,483,648 ≤ A, B ≤ 2,147,483,647)

출력

첫째 줄에 답을 출력한다. (-2,147,483,648 ≤ 답 ≤ 2,147,483,647)

풀이

제가 작성한 글중의 https://jow1025.tistory.com/35 의 첫번째 공식을 이용하면 되고, a>b일 때만 고려해주면됩니다.

코드

#include<iostream>
using namespace std;
int main()
{
	long long a, b;
	cin >> a >> b;
	if (a <= b)
		cout << (b - a + 1) * (b + a) / 2;
	else
		cout << (a - b + 1) * (b + a) / 2;
}

결과