코딩무식자 전공생

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

문제

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다. 

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다. 

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에  준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1≤A≤B 이다.  

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째  날에는 41개이다. 따라서 A=2, B=7 이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

입력

첫째 줄에는 할머니가 넘어온 날 D (3≤D≤30)와 그 날 호랑이에게 준 떡의 개수 K (10≤K≤100,000)가 하나의 빈칸을 사이에 두고 주어진다. 

출력

첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다. 

풀이

수학을 잘하는사람이 코딩도 잘 한다는 것을 느낀 문제입니다. 문제의 조건을 수식에맞게 변수로 식을세워서 풀면 금방 답이 구해지는 문제인데, 아직 그런 학습이 부족해서인지 다른분들의 코드를 보고서야 이해를 했습니다.  이런 부류의 문제를 많이 풀어봐야겠습니다.

풀이는 스폐셜 저지, 즉 답이 여러개 일 수 있다는 점, 그래서 첫날(a)과 둘째날(b)을 1로잡고 하나씩 탐색해도되는점, 문제가 피보나치의 패턴이라는것만 알면 쉽습니다......

규칙을 보죠. 피보나치패턴에의해  첫날에 a, 둘째날에b만큼 주니, 다음과같이 식을 만들 수 있습니다.

a->b->a+b->a+2b->2a+3b..... 

a가 1,b=1부터 가정하므로(답이 여러개일 수 있으니 쉽게 a,b가 1개라고 가정하면서 탐색해본다는 마인드) k에 대한식을 세워보면 k=fibo[d-2]*a+fibo[d-1]*b입니다. 이 식을 세울줄 아는 능력(수학적 재능...)만있으면 끝입니다. 여기서 중요한건 a를 구하고 b를 구한다는 것, fibo[d-2],fibo[d-1]은 각각 a에대한 비율,b에대한 비율이라는것입니다. a는 1부터탐색해보고, 이때 가정한 a에 대해 b에대한 식b=(k-a*fibo[n-1])%fibo[n-2])을 세워서 b에대한 식이 나누어 떨어지면 (갯수는 정수이므로)a와 b가 구해진 겁니다. 끝입니다.

코드

#include<iostream>
using namespace std;
int fibo[31];
int main()
{
	int d, k;
	cin >> d >> k;
	fibo[1] = fibo[2] = 1;
	for (int i = 3; i <= d; i++)
	{
		fibo[i] = fibo[i - 2] + fibo[i - 1];
	}
	//a와 b의 계수(비율)
	int a_profit = fibo[d - 2];
	int b_profit = fibo[d - 1];
	//k=fibo(d-2)a+fibo(d-1)b;
	int a, b;
	for (int i = 1;; i++)
	{
		//a는 1부터 탐색해본다.
		a = i;
		//b에대한 식에대해 나누어떨어지면 답 구한거임)
		if ((k - a_profit * a) % b_profit)
			continue;
		//이 때 b는 구해진 a에대해 구함.
		b = (k - a_profit * a) / b_profit;
		break;
	}
	cout << a << endl << b << endl;
}

결과

중학교, 고등학교 수학시간에 배우고 써먹었던 간단한 공식들이지만 코딩에 적용해야할 때 까먹는 경우가 빈번한 것 같아서 몇가지 수학 공식들을 적어둡니다.(계속 추가 및 수정할 예정입니다.)

의외로 모르면 문제를 못 풀거나 어려움에 처할 수 있는 공식들입니다.

백준사이트의 c++기초문제집을 처음부터 풀다보면 마주칠 수 있는 공식들입니다.

1.  두 수 사이의 합 (합공식)(등차수열일때만.)

1부터 n까지의 합 공식은 n(n+1)/2 입니다.

그러면 5부터7까지(n부터 m까지의합) 합은 7(7+1)/2일까요? 아닙니다.

 n(n+1)/2을 풀어써보면 (수의 갯수) * (끝수+첫번째 수) / 2입니다.

정답률 25%문제풀기

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

결론

n~m까지의 합 : (n부터 m까지의 갯수) * (n+m) / 2 

ex) 5부터7까지의합 : 3*(5+7)/2=18

2. 다각형의 대각선의 갯수

n각형,n>=3일때 n(n-3)/2

3. 삼각형의 조건

세 변 a,b,c 이고 가장 긴 변이 c일때

a+b>c (역으로, 삼각형이 아니려면? a+b<=c)

https://www.acmicpc.net/problem/1448

++피타고라스의정리

세 변 a,b,c이고 c가 직각을 바라보는 변 일 때 

4. 등차수열, 등비수열

등차: 숫자간의 간격(차,d), 첫 수: a ,n번째 수 

일반항: a+(n-1)d

등비: 숫자간의 간격(곱,r), 첫 수:a, n번째 수

일반항: ar^(n-1)

5. 원의 위치관계(내접,외접)★★

머리가 좋으시다면 외워놓는게 좋지만 그게아니라면 직접 두 원을 그려보면서 이해하는게 제일 좋습니다.

(r:반지름길이, d: 두 원의 중심사이의 거리)

출처https://mathbang.net/101

원의 위치관계를 이용한 정답률 19퍼센트짜리의 문제입니다. 모르면 못풀고 알면 공식만 작성해서 제출하면됩니다.

https://www.acmicpc.net/problem/1002

6. 기울기, y절편 구하기

두 점(x1,y1),(x2,y2)가 주어질 때

기울기: (y2-y1) / (x2-x1)

y절편: 기울기구하고 주어진 좌표 중 아무거나 대입하여 y절편을 구함

7. 조합,순열 ★★★(스택,재귀,dfs, 백트래킹)

조합: nCm = n! / m! = (n-m)! / m! (단 m=0일떄 답 1)

순열 nPm =n! / (n-m)! (단 m=0일때 답1)

조합에서,  mCn = m-1Cn-1 + m-1Cn

이 공식으로 풀 수 있는 dp문제

https://www.acmicpc.net/problem/1010

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

문제

꿍은 오늘 학교에서 삼각형에 대해 배웠다. 삼각형은 변의 길이에 따라 다음과 같이 분류될 수 있다.

• 정삼각형(equilateral triangle)은 모든 변의 길이가 같다. 각 역시 60도로 모두 같다.
• 이등변삼각형(isosceles triangle)은 두 개의 변의 길이가 같다. 각 역시 두 개의 각의 크기가 같다.
• 부등변삼각형(scalene triangle)은 모든 변의 길이가 같지 않다. 각 역시 모두 다르다. 몇몇 부등변삼각형의 경우 직각삼각형이다.

수학선생님이 삼각형의 세 변의 길이를 가지고 삼각형을 분류하라는 숙제를 내줬는데 꿍은 정말 놀고싶다. 꿍이 놀수있도록 여러분이 도와주어라.

입력

입력의 첫 줄에는 테스트케이스의 개수 T(1 <= T <= 100)가 주어진다. 다음 T줄에는 각 줄에 삼각형의 세 변을 나타내는 3개의 정수 A,B,C(1 <= A,B,C <= 1,000,000)가 주어진다.

출력

각 테스트 케이스에 대해 삼각형이 “equilateral”, “isosceles”, “scalene” 타입 중 어느 타입에 속하는지 출력한다. 만약 주어진 세 변의 길이로 삼각형이 만들어지지 않을경우, “invalid!”를 출력한다.

풀이

정답률이 51프로 밖에안되는것은 주어진 삼각형의 종류에대해서만 생각했기때문이라고 생각합니다.

기본적으로 삼각형의 조건은 a<=b<c일때 a+b>c입니다. 역으로 a+b<=c일 때 삼각형은 성립불가합니다.

삼각형의 조건을 만족시키지 않을 때만 invalid를 출력하고 이어서 조건의 삼각형들에 대해 else,if로 분기시키면됩니다.

if 정삼각형일때, else if 이등변삼각형일때, else if 부등변삼각형일 때 else "invalid" 이런식으로 작성하면 오류가뜹니다. (else는 무조건 삼각형이 아닐때만.)

*부등변삼각형: 정삼각형, 이등변삼각형도 아닌 삼각형

코드

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int t;
	cin >> t;
	int a[3];
	for(int i=1;i<=t;i++)
	{
		cin >> a[0] >> a[1] >> a[2];
		sort(a, a + 3);
		cout << "Case #" << i << ": ";
		if (a[0] + a[1] <= a[2])cout << "invalid!";
		else if (a[0] == a[1] && a[1] == a[2])
			cout << "equilateral";
		else if (a[0] == a[1] || a[1] == a[2] || a[0] == a[2])
			cout << "isosceles";
		else cout << "scalene";
		cout << endl;
	}
}

결과