코딩생존기

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

처음에는 문제를 이해하지 못했었는데 지그재그로 이해하기보다는 대각선으로 보는게 이해하기 쉽다. 몇번째 대각선에 속해있는 분수인지 구하고 짝수번째 대각선이면 위에서 아래로 가고 홀수번째 대각선이면 아래에서 위로 가기때문에 몇번째 분수인지만 알면 분모와 분자를 구해서 출력해주면 된다.

정답코드

#include "iostream"

using namespace std;

int main()
{
	// d: 현재 대각선 번호 , cnt : 분수의 총 개수
	int x, d = 1, cnt = 0;

	cin >> x;

	//대각선에 속하는 개수까지 증가시켜줌
	while (cnt+d < x)
	{
		cnt += d;
		d++;
	}

	//순서-지금까지의 분수 개수 = 위치
	int idx = x - cnt;
	int answer_x, answer_y;				//분자, 분모

	//짝수이면 아래 홀수이면 위로 감
	if (d % 2 == 0)
	{
		answer_x = idx;
		answer_y = d - idx + 1;

	}
	else
	{
		answer_x = d - idx + 1;
		answer_y = idx;
	}

	cout << answer_x << "/" << answer_y << endl;

	return 0;
}

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

5킬로그램 봉지를 최대한 쓰고 나머지에 3킬로그램 봉지를 쓰면서 정확하게 N그램에 맞춰야한다. 그게 불가능하다면 -1을 출력해준다.

정답코드

#include "iostream"

using namespace std;

int main() {
    int n;
    cin >> n;

    int cnt = 0;

    
    while (n >= 0) {
        if (n % 5 == 0) {  // 5로 나누어 떨어지면
            cnt += n / 5;  // 5kg 봉지 개수 더함
            cout << cnt << endl;
            return 0;
        }
        n -= 3;  // 5로 나누어 떨어지지 않으면 3kg 봉지를 하나 사용
        cnt++;  // 3kg 봉지 사용했으므로 봉지 개수 추가
    }

    // 만약 정확히 N kg을 만들 수 없으면 -1 출력
    cout << -1 << endl;
    return 0;
}

정답코드2 

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

연립방정식을 풀면되는 문제이다. x,y가 각각 -999 ~ 999까지이기 때문에 반복문을 통해 연립방정식에 맞는 x,y 값을 구해도 1초안에는 해결할 수 있을 것이라고 생각해서 그렇게 풀어보았다.

여기서 최적화를 해보자면 수학적인 방법을 통하여 x,y를 구해보자. 이때 크래머의 법칙을 사용하면 된다. 크래머의 법칙은  2개의 미지수를 포함하는 2개의 방정식을 행렬로 나타내고, 이를 통해 해를 구하는 방식이다. 

행렬연산을 통해 도출 된 위의 식을 풀면 되는 것이다. 이떄 ae-bd는 0이 아니어야한다.

정답코드

#include "iostream"

using namespace std;

int main()
{
	int a, b, c, d, e, f;

	cin >> a >> b >> c >> d >> e >> f;

	for (int x = -999; x <= 999; x++)
	{
		for (int y = -999; y <= 999; y++)
		{
			if ((a * x + b * y) == c && (d * x + e * y) == f)
			{
				cout << x << " " << y << endl;
				break;
			}
		}
	}

	return 0;
}

정답코드2 - 크래머의 법칙사용

#include <iostream>

using namespace std;

int main() {
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;

    int denominator = a * e - b * d;

    // 분모가 0이 아닌 경우에만 해가 존재함
    if (denominator != 0) {
        int x = (c * e - b * f) / denominator;
        int y = (a * f - c * d) / denominator;

        cout << x << " " << y << endl;
    }

    return 0;
}

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

처음에 풀어본 방법은 n까지 순회하면서 자리수의 합과 해당 수의 합이 n과 같으면 답으로 여기고 출력해주게 했다. 

하지만 최적화를 해본 방법은

100만까지의 수를 생각했을 때 자리 수의 최대합은 999999 를 모두 더했을 때의 합인 54이기 때문에

이를 빼두고 n까지 순회하면서 자리수의 합을 계산하면 1부터 순회하는 것보다는 나은 시간이 나올 것이다.

정답코드1

#include "iostream"

using namespace std;

int main()
{
	int n, sum, answer;

	cin >> n;

	for (int i = 1; i < n; i++)
	{
		int s = i;
		sum = 0;
		while (s > 0)
		{
			//자리수의 합과 그 수 더하기
			sum += s % 10;
			s /= 10;
		}
		if ((sum + i) == n) {
			answer = i;
			break;
		}
	}

	cout << answer << endl;

	return 0;
}

정답코드(최적화)

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    int answer = 0;

    // n - 54부터 n까지 탐색 (자리수 최대합이 54이므로)
    for (int i = max(1, n - 54); i < n; i++) {
        int s = i, sum = i;

        // 자리수의 합을 더함
        while (s > 0) {
            sum += s % 10;
            s /= 10;
        }

        // 생성자 찾음
        if (sum == n) {
            answer = i;
            break;
        }
    }

    cout << answer << endl;
    return 0;
}

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

3장의 카드를 조합했을 때 M을 넘지 않으면서 M에 최대한 가까운 카드의 합을 출력해줘야한다. N이 100까지로 크지 ㅇ낳아 3중 반복문으로 조합을 구현해도 시간복잡도가 괜찮을 것 같아서 M보다 작은 합중에 제일 큰 합을 구한 다음 출력해주었다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> cards(n);
    for (int i = 0; i < n; i++) {
        cin >> cards[i];
    }
    
    int max_sum = 0;  // M을 넘지 않으면서 가장 가까운 합을 저장
    
    // 세 장의 카드를 고르는 모든 경우를 탐색
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                int sum = cards[i] + cards[j] + cards[k];
                
                // 합이 M을 넘지 않는지 확인하고, M과 가장 가까운 합을 저장
                if (sum <= m && sum > max_sum) {
                    max_sum = sum;
                }
            }
        }
    }
    
    cout << max_sum << endl;
    return 0;
}

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

육각형 벌집 구조에서 1에서 N번째 방으로 갈때 최소 몇개의 방을 지나는지 구하면 되는 문제이다. 최소 거리로 가려면 

일직선으로 가야하는데 이렇게 되면 시작에서 몇개의 껍질을 이동하는지 구하면 된다. 일단 껍질은 육각형으로 껍질이 

늘어날 때 몇개의 수가 늘어나는지 알아보면 된다. 육각형이 커질수록 6의 배수로 수가 늘어나는 것을 볼 수 있다. 이를 

바탕으로 코드를 작성해보자

정답코드

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;

    // 1번 방은 자기 자신이므로 예외 처리
    if (N == 1) {
        cout << 1 << endl;
        return 0;
    }

    int layer = 1; // 현재 몇 번째 껍질인지 나타냄
    int end_of_layer = 1; // 각 껍질의 마지막 방 번호

    // N번 방이 포함된 껍질을 찾음
    while (end_of_layer < N) {
        end_of_layer += 6 * layer; // 다음 껍질의 마지막 방 번호
        layer++;
    }

    // 껍질 번호가 곧 지나가는 방의 수
    cout << layer << endl;

    return 0;
}

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

조건을 먼저 살펴보자 

넓이가 양수인 삼각형을 만들어야 하고, 삼각형의 둘레가 최대가 돼야한다.

일단 삼각형이 되려면 제일 긴 막대가 나머지 두 막대의 합 보다 작아야 하기 때문에

입력을 받은 후 배열에 저장한 다음 정렬해주고 제일 긴 막대의 길이 부터 그 다음으로 작은 막대 길이까지 반복문을 돌면서 이 조건을 먼저 검사해주자.

만약 제일 긴막대가 해당 조건을 만족한다면 break 해주면 그게 둘레의 최대값이 된다.

정답코드

#include "iostream"
#include "algorithm"

using namespace std;

int main()
{
	int a, b, c;

	cin >> a >> b >> c;

	// 세 변을 정렬하여 가장 긴 변이 마지막에 오도록 정렬
	int sides[3] = { a, b, c };
	sort(sides, sides + 3);

	for (int i = sides[2]; i >= sides[0]; i--)
	{
		if (i < sides[0] + sides[1])
		{
			sides[2] = i;
			break;
		}
	}

	int sum = sides[0] + sides[1] + sides[2];

	cout << sum << endl;
}

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

 while문을 돌면서 조건을 검사하고 그에 맞는 결과를 출력해주면 된다. 삼각형의 조건을 제일 먼저 검사해주면 되는데 배열을 선언해주고 이를 정렬해서 마지막 값과 앞의 두 값의 합을 비교해주면 된다. 나머지도 조건대로 해주면 된다.

정답코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int a, b, c;

    while (true) {
        cin >> a >> b >> c;

        // 종료 조건
        if (a == 0 && b == 0 && c == 0) break;

        // 세 변을 정렬하여 가장 긴 변이 마지막에 오도록 정렬
        int sides[3] = {a, b, c};
        sort(sides, sides + 3);

        // 삼각형의 조건 검사: 가장 긴 변이 다른 두 변의 합보다 작아야 함
        if (sides[2] >= sides[0] + sides[1]) {
            cout << "Invalid" << endl;
        } else if (sides[0] == sides[1] && sides[1] == sides[2]) {
            cout << "Equilateral" << endl;
        } else if (sides[0] == sides[1] || sides[1] == sides[2]) {
            cout << "Isosceles" << endl;
        } else {
            cout << "Scalene" << endl;
        }
    }

    return 0;
}

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

3개의 각 크기를 조건문으로 검사해서 각 조건에 맞는 문자열을 출력해주면 된다. 

먼저 합이 180인지 확인하고 아니라면 밑의 조건들을 다시 검사해주는 식으로 조건문을 구성해주면 된다.

정답코드

#include "iostream"

using namespace std;

int main()
{
    int a, b, c;

    cin >> a >> b >> c;

    if (a + b + c != 180)
        cout << "Error" << endl;
    else
    {
        if (a == 60 && b == 60 && c == 60)
            cout << "Equilateral" << endl;
        else if (a == b || b == c || a == c)
            cout << "Isosceles" << endl;
        else
            cout << "Scalene" << endl;
    }

    return 0;
}

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

봤을 때, 처음 생각난 것이 최소 최대 x,y값을 구해서 넓이를 구하면 될 것 같다였다. 옥구슬을 보면 최소값과 최대값을 구해서 넓이를 구하면 점을 모두 둘러싸기 때문에 괜찮을 것 같다.

정답코드

#include "iostream"
#include "algorithm"

using namespace std;

int main()
{
	int n;
	int max_x = -10000, max_y = -10000, min_x = 10000, min_y = 10000;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		max_x = max(x, max_x);
		min_x = min(min_x, x);
		max_y = max(y, max_y);
		min_y = min(min_y, y);
	}

	long long sum = (max_x - min_x) * (max_y - min_y);

	cout << sum << endl;

	return 0;
}