코딩무식자 전공생

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

풀이

도대체 어떻게 풀 수 있는 문제일까 고민을 많이 했는데 딱히 떠오르지 않아서 구글링을 통해 10은 2*5으로 이루어진다는 힌트만 얻고 대충 1!부터 10!부터 노트에 적어보며 규칙성을 찾아보았습니다. (사실 위의 힌트가 정답의 전부입니다.)

1!= 1*1

2!= 2*1

3!= 3*2*1

4!= 4*3*2*1

5!= 5*4*3*2*1

6!= 6*5*4*3*2*1

7!= 7*6*5*4*3*2*1

8!= 8*7*6*5*4*3*2*1

9!= 9*8*7*6*5*4*3*2*1

10!= 10* 9*8*7*6*5*4*3*2*1

이렇게 펼쳐본다음 위에서 얻은 힌트를 이용해서 팩토리얼을 구성하는 숫자들을 2와 5로 쪼개어 보았습니다. 그리고 쪼갠 숫자들을 나열하여 2와 5가 각각 몇번 나오는 지를 세어보았습니다.

2!= 2*1 => 2: 1개, 5: 0개

3!= 3*2*1 => 2: 1개, 5: 0개

4!= 2*2*3*2*1 => 2: 3개, 5: 0개

5!= 5*2*2*3*2*1 => 2: 3개, 5: 1개

6!= 2*3*5*2*2*3*2*1 => 2: 4개, 5: 1개

7!= 7*2*3*5*2*2*3*2*1 => 2: 4개, 5: 1개

8!= 2*2*2*7*2*3*5*2*2*3*2*1 => 2: 7개, 5: 1개

9!= 9*2*2*2*7*2*3*5*2*2*3*2*1 => 2: 7개, 5: 1개

10!= 2*5*9*2*2*2*7*2*3*5*2*2*3*2*1 => 2: 8개, 5: 2개

1!~ 10! 까지 계산된 수를 모두 구해서 정답을 구해보면 위의 규칙성 중 팩토리얼 숫자 중 2로 구성된 수의 갯수와 5로 구성된 수의 갯수 중 더 적은 갯수와 일치함을 알 수 있습니다.

알고리즘을 알았으니 반복문을 통해 식을 작성할 텐데 각 팩토리얼 수의 2와 5의 갯수를 구하는 식은 아래 소스코드에 나와있습니다.

코드

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

풀이

영어로된 문제라 당연스럽게 구글번역으로 한글로 바꿔서 풀었습니다ㅋㅋ;

문제를 요약하면, N의 자릿값을 계속 더해나갈 때 그 값이 언젠간 1이 되면 Happy number가 되고, 아닐 시 Unhappy number가 됩니다.

아닐 경우 문제에서 예로 들어준 5를 보면

5-> 25-> 29-> 85-> 89-> 145-> 42-> 20->4->16->37->58->89->----- 순으로 이어지는데 결국 기존에 나왔던 89가 또한번 나타나므로 

결국,  수식을 계속 계산해나갈 때 기존의 값이 또 나오면 Unhappy number임을 알 수 있습니다.

핵심은 한번 계산할 때 마다 담아놨던 값들에 대해서 일일히 또 나타나는 값인지 확인해야한다는 것입니다.

그 과정에서 주석 친 29~31행위치에 코드를 작성하지 않도록 주의하면 될 것 같습니다.

코드

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

분류는 수학으로되어있는데 규칙찾기문제같네요...

풀이

문제를 잘 이해하셔야합니다. 단순히 연속된 좌표가 '.'일때만 체크해주면 좋겟지만, 예외상황이 존재합니다.

대표적으로 ..XX..일때입니다.(세로표현도 똑같음.) 이 경우, 가로로보면 누울자리가 1개가 아니라 2개입니다. 이 예외만 처리해주면되고, 저 같은 경우 현재 좌표가 '.'일때, 'X'일때로 나눠서 row와 col값을 계산했습니다.

코드

결과

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

문제

크기가 N인 수열 A가 주어졌을 때, 세준이는 인접한 두 원소의 차이를 이용해서 크기가 N-1인 수열 B를 만들 수 있다.

예를 들어, A = {5,6,3,9,-1} 이었을 때, B = {6-5, 3-6, 9-3, -1-9} = {1,-3,6,-10}이 된다. 다른 말로 B[i] = A[i+1]-A[i]가 된다.

수열 A가 주어졌을 때, 세준이가 위의 방법을 K번 했을 때 나오는 수열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N과 K가 주어진다. N은 20보다 작거나 같은 자연수이고, K는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 둘째 줄에는 수열이 ‘,’로 구분되어 주어진다.

출력

첫째 줄에 K번 변형한 수열을 ‘,’로 구분하여 출력한다.

풀이

한 턴이 지날때 마다 저장된 값의 개수가 한개씩 줄어들어서 이 요소들을 어떻게 담을까 고민한문제입니다. 결국은 규칙만 찾아서 이중 반복문으로

해결 할 수 있었고 간단한 문제였습니다.

조건에 맞게 배열index로 입력받고 k번 수행 할 때 남은 요소들을 출력할 차례인데, 이 때 규칙을 보면 n개의 요소는 k(1부터시작)가 증가 할 때 마다 한개 씩 줄어듭니다. 

ex)k가 3일 때 

5,6,3,9,-1 -> 1,-3,6,-10 (4개) -> -4,3,-16 (3개) -> 7,-19 (2개)

즉, i~k번 연산하는 동안 n개의 요소들이 각각 변화하는 과정을 연산하되, 한번의 연산 후 요소의 개수가 한개 씩 줄어들어야합니다. 

결론적으로 18행이 그 연산코드입니다. 연산 후 조건에 맞게 출력하면됩니다.

코드

#pragma warning(disable:4996)
#include<iostream>
using namespace std;
int arr[21];
int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		if (i < n - 1)
			scanf("%d,", &arr[i]);
		else
			scanf("%d", &arr[i]);
	}
	for (int i = 0; i < k; i++)
	{
		for (int j = 0; j <n-1-i;j++)
		{
			arr[j] = arr[j + 1] -arr[j];
		}
	}
	cout << arr[0];
	for (int i = 1; i < n - k; i++)
		cout << ',' << arr[i];
	cout << endl;
}

결과

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

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

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

출력

첫째 줄부터 차례대로 별을 출력한다.

풀이

별찍기를 풀 때 마다 느끼지만 재귀를 사용한 고난이도의 별찍기문제가 아닌이상 90%가 i,j를 이용한 연산만으로도 풀리는것같습니다.

즉, 별찍기를 어려워하는것은 아직 규칙성을 발견하여 코딩하는 연습이 부족하다는 것입니다.( 풀 때 마다 실력이 늡니다.) 문제를 살펴보면, 행의 갯수는 n*2, 한개의 열에 등장하는 공백+별의 갯수는 1~n개 라는 것을 알아야합니다. 그리고, 별이 찍히는 위치가 행마다 달라지는데, 행이 홀수냐 짝수냐에 따라, 그리고 그 때의 현재 열이 홀수냐 짝수냐에 따라 별과 공백의 위치가 엇갈리는 것을 확인할 수 있습니다. 코드로 옮기면 끝입니다.

코드

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n * 2; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i % 2 == 0)
			{
				if (j % 2 == 0)
					cout << "*";
				else cout << " ";
			}
			else
			{
				if (j % 2 == 0)
					cout << " ";
				else cout << "*";
			}
		}
		cout << endl;
	}
}

결과

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

문제

무엇이든 덮어버리는 것을 좋아하는 지은이는 한변의 길이가 A인 정삼각형을 한변의 길이가 B인 정삼각형으로 완전히 덮어 버리고자 한다. 

두개의 정수 A, B 가 주어지고, B ≤ A 이고, A를 B로 나눌수 있을때, 한 변의 길이가 A인 정삼각형을 완전하게 덮기 위한, 한변의 길이가 B인 정삼각형의 개수를 구하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (T ≤ 1000)

각각의 테스트 케이스는 한줄로 이루어져 있으며 두개의 정수 A, B 가 (1 ≤ B ≤ A ≤ 1,000,000, B|A) 주어진다.

출력

각 테스트 케이스마다 한변의 길이가 A인 정삼각형을 완벽하게 덮을 수 있는 한변의 길이가 B인 정삼각형의 최소 개수를 출력한다.

풀이

규칙찾기문제입니다. 노트에 알고리즘을 설계하고 그것을 소스코드로 구현하는 능력을 기르기 위해 일부러 노트에 카테고리명을 노트에풀기라고 지었습니다.

규칙을 찾아볼까요? (그려보면 암) 2 1 일 때 답=4, 3 1 일때 답=9,  4 1 일때 답=16 입니다. 따라서 b가1일때 정답은 a^2이죠. 그리고 문제조건에의해 a%b=0이어야하므로  4 2일때를보면 4, 그리고 6 2 일 때를보면 9, 6 3일때는 4입니다. 결국 정답은 (a/b)^2가됩니다. 주의할것은 int형범위를 넘길 수 있으므로 longlong형으로 정답을 출력해야합니다.

코드

#pragma warning(disable:4996)
#include<iostream>
using namespace std;
int main()
{
	int t;
	long long a, b;
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{
		scanf("%lld%lld", &a, &b);
		printf("%lld\n", a / b * a / b);
	}
}

결과