동바리의 공부방

링크 : 2512번: 예산 (acmicpc.net)

코드 :

import sys
input = sys.stdin.readline
N = int(input())
member = list(map(int, input().split()))
total_money = int(input())
start = 0
end = max(member)

mid = 0
mid_val = 0

while (start <= end):
    mid = int((start + end) / 2)
    sum = 0
    for i in range(0, len(member)):
        sum += min(member[i], mid)

    if (sum > total_money):
        end = mid - 1
    else:
        start = mid + 1
        mid_val = max(mid_val, mid)
        #print(mid_val)

print(mid_val)

1. 상한선을 잘 선택해야 풀 수 있는 문제였습니다.
2. 상한선 선택은 이진탐색으로 진행합니다.
3. 상한선을 선택했다면 min 함수를 이용해 지방에게 줄 돈을 선정합니다.
4. 만일 상한선보다 작은 요청금액이라면 요청금액대로 줄 것이고, 상한선보다 큰 요청금액이라면 상한선만큼 줍니다. 이 때 내어준 총 금액은 sum 변수에 저장합니다.
5. sum 변수가 줄 수 있는 금액보다 크다면 배제합니다.
6. sum 변수가 줄 수 있는 금액보다 크거나 작다면 해당 상한선을 저장하고, 이 상한선보다 더 큰 상한선이 있는지 mid를 조정하며 찾습니다.

문제 :

2116번: 주사위 쌓기 (acmicpc.net)

#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_SQUARE_MAX_CNT (10000 + 1)
#define dice_kind_cnt      (6 + 1)
vector<uint32_t>         square_vec[MAX_SQUARE_MAX_CNT];
uint32_t                 square_cnt;
uint32_t                 max_ans                         = 0;
uint32_t                 maxNum_arry[MAX_SQUARE_MAX_CNT] = {0};
uint32_t                 compatible[6 + 1]               = {0};

void Run(const uint32_t under_num, const uint32_t curr_layer,
              uint32_t sum) {
    if (curr_layer > square_cnt) {
        if (max_ans < sum) {
            max_ans = sum;
        }

        return;
    }

    uint32_t upper_num     = 0;
    for (int i = 1; i <= 6; i++) {
        if (square_vec[curr_layer][i] == under_num) {
            upper_num = square_vec[curr_layer][compatible[i]];
            break;
        }
    }

    int nowmax = 6;
    while (true) { // 지금 행에서 옆면최대값 찾는 과정
        if (nowmax != upper_num && nowmax != under_num)
            break;
        else
            nowmax--;
    }

    Run(upper_num, curr_layer + 1,
        sum + nowmax);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> square_cnt;
    for (size_t i = 1; i <= square_cnt; ++i) {
        square_vec[i].resize(7);
        for (uint32_t j = 1; j <= 6; j++) {
            uint32_t temp;
            cin >> square_vec[i][j];
        }
    }

    compatible[1] = 6, compatible[6] = 1;
    compatible[2] = 4, compatible[4] = 2;
    compatible[3] = 5, compatible[5] = 3;

    // 어느면이 윗면인지 고려되있지 않음.
    for (size_t i = 1; i <= 6; i++) {
        Run(square_vec[1][i], 1, 0);
    }

	cout << max_ans << '\n';

    return 0;
}

초등학생 수준의 문제라니.... 예제는 맞았지만, 정답은 아니었어서 아래 링크의 코드를 참고했습니다. 제 아이디어와 동일했지만, 제 코드는 답이 아니었어서... ㅜ

​

백준2116-주사위쌓기 java (tistory.com)

​

문제를 정확히 이해하지 못해, 처음엔 아예 틀린 방법으로 접근했었네요. 그래서 정답이 계속 30이 나왔었지만, 힌트를 보고 그게 아닌것을 알았습니다.

​

아랫면의 숫자와 매칭되는 숫자가 다음 층의 주사위의 아랫면이 된다는 것을 유념하시면 됩니다.

import sys

MAX = 1000
def main():
    T = int(input())
    while (T > 0) :
        T = T - 1
        start_x, start_y, end_x, end_y = map(int, input().split())
        in_out_cnt = 0
        planet_cnt = int(input())
        for i in range(0, planet_cnt) :
            planet_x, planet_y, radius = map(int, input().split())
            if ((start_x - planet_x) * (start_x - planet_x) + (start_y - planet_y) * (start_y - planet_y) < radius * radius):
                if ((end_x - planet_x) * (end_x - planet_x) + (end_y - planet_y) * (end_y - planet_y) > radius * radius):
                    in_out_cnt = in_out_cnt + 1
                    continue

            if ((end_x - planet_x) * (end_x - planet_x) + (end_y - planet_y) * (end_y - planet_y) < radius * radius):
                if ((start_x - planet_x) * (start_x - planet_x) + (start_y - planet_y) * (start_y - planet_y) > radius * radius):
                    in_out_cnt = in_out_cnt + 1
                    continue

        print(in_out_cnt)

main()

1004번: 어린 왕자 (acmicpc.net)

1. 문제의 설명은 장황했지만, 결국 시작지점과 종료지점이 각각 몇개의 원 안에 있는지 물어보는 문제였습니다.
2. 각각 몇개의 원안에 있는지 수학 공식을 이용해서 풀 수 있었습니다.
3. 다만, 시작지점과 종료지점이 같은 원 안에 있음을 주의해서 풀이해야 합니다.

https://learnopengl.com/Introduction

Introduction

당신이 여기 온 이후로, 당신이 아마 컴퓨터 그래픽스의 내부 동작을 배우기 위함일 것입니다. 그리고 멋진 아이들이 스스로 하는것을 모든것을 당신 스스로 하고싶어할 것입니다.

​

Prerequisities

OpenGL은 그래픽스 api이지 그것 자체로 플랫폼인 것은 아니기 때문에, OpenGL은 작동하기 위한 언어를 필요로 하고 그 선택은 C++입니다. 그러므로 c++ 프로그래밍 지식은 요구됩니다. 하지만 나는 설명하기 위해 노력할 것입니다. 사용되는 대부분의 컨셉들, advanced된 c++ 토픽들. 그렇다고 c++ 전문가가 되기를 요구하지는 않습니다. 그러나 당신은 "Hello World"를 출력하는 것 이상을 알야아 합니다. 당신이 c++에 대한 경험이 많이 없다면 난 아래 링크를 추천합니다.

http://www.learncpp.com/

또한 우리는 몇몇 수학(linear algebra, geometry, and trigonometry)을 사용할 예정이고 나는 필요로 하는 수학의 요구되는 개념 모두를 설명하기 위해 노력할 것입니다. 하지만 난 수학자가 아닙니다. 내 설명이 이해하기 쉽더라도. 그렇기에 나의 설명이 불완전할 수 있습니다. 그래서 필요로 하는 곳에는 내가 좋은 resource를 제공할 것입니다.

필요로 하는 수학적 지식에 대해 겁먹지 마세요. OpenGL로의 여행을 시작하기도 전에.

대부분의 수학적 지식 개념은 기본 수학 배경만 가지고 있다면 이해할 수 있고 나는 수학이 최소한이 될 수 있게끔 노력할 것입니다.

심지어, 대부분의 기능은 당신이 모든 수학을 이해하라고 요구하지도 않아요. 당신이 그것을 어떻게 사용하는지 알고 있다면요.

​

Structure

LearnOpenGL은 많은 섹션으로 나뉩니다. 각각의 세션은 몇몇 챕터를 포함하고 있습니다. 이 챕터는 각각 다른 개념을 자세히 (in large detail)설명합니다. 각각의 챕터는 왼쪽 메뉴에서 확인할 수 있습니다. 그 개념들은 순차적으로 설명될 것입니다. 각각의 챕터는 배경지식 이론과 실전적 관점을 설명합니다.

​

개념들이 더 쉽게 따라올 수 있게 만들기 위해 그리고 그들에게 몇몇의 추가적인 스트럭쳐를 주기 위해 , 그 책은 boxes, code blocks, color hints 그리고 function refrerences를 포함합니다.

​

green boxes는 몇몇 노트들과 유용한 특성, 힌트(OpenGL에 대한 또는 subject에 대한) 포함합니다.

​

red boxes는 경고 또는 다른 특성 (매우 주의해야하는)을 포함합니다.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
vector<int> my_vector;
bool visited[10000 + 1];
int ans[10000 + 1];

void Run(const int start_idx, const int depth)
{
	if (visited[start_idx]) {
		return;
	}

	visited[start_idx] = true;
	ans[depth] = my_vector[start_idx];
	if (depth == M - 1) {
		for (int i = 0; i < M; i++) {
			cout << ans[i] << ' ';
		}

		cout << '\n';
		visited[start_idx] = false;
		return;
	}
	
	for (int i = 1; i < my_vector.size(); i++) {
		Run(i, depth + 1);
	}
	visited[start_idx] = false;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N >> M;
	my_vector.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> my_vector[i];
	}

	sort(my_vector.begin(), my_vector.end());

	if (M == 1) {
		for (int i = 1; i <= N; i++) {
			cout << my_vector[i] << '\n';
		}

		return 0;
	}

	for (int i = 1; i <= N; i++) {
		Run(i, 0);
	}
}

1. 재귀함수를 이용하여 풀 수 있는 문제였습니다.
2. 지금 코드의 경우는 main 함수에서 Run을 N번 실행합니다.
3. 하지만 이런 방식 말고, main 함수에서 Run 함수를 한 번만 실행하고 Run 내에서 여러번 호출하는 방식으로 코딩을 고쳐봐야 할 것 같습니다.