본문 바로가기

[C, C++ 알고리즘]7

[백준 1005] ACM CRAFT 주어진 순서가 있고, 건물마다 걸리는 시간이 있다. 그럼 순서를 정리하고 목표 건물을 짓기 위해 필요한 다른 건물들의 최대로 걸리는 시간을 목표 건물이 지어지기까지 걸리는 시간에 더하면 되는 것이다. 문제에서 들어준 예를 가지고 설명을 해보자면... 목표는 4번. 4번은 2가지의 건물을 지어야만 지어질 수 있다. 그러면 2가지의 건물 중 가장 오래 걸리는 건물의 시간은 3번 100초 이다. 이를 3번과 2번에도 적용하고 쭉쭉해보면 120초라는 걸 알 수 있다. 순서 정렬 -> 건물 직전 단계의 건물들의 건설 시간 중 가장 오래 걸리는 걸 택함 반복해서 시작점까지 왔으면 목표건물의 지어지는 시간 까지 합하면 끝. #include #include #include using namespace std; int .. 2021. 11. 13.
[백준 1004] 어린 왕자 진입/이탈을 몇번하는지 구하는 문제다. 진입/이탈을 하는 것 --> 행성계 내부와 외부에 출발점과 도착점이 각각 하나씩 있을 때 쉽죠? 행성계의 중심과 출발/도착점 사이의 거리와 반지름의 길이를 비교하면 외부에 있는지 내부에 있는지 알 수 있다. 그러면 출발점과 도착점이 외부, 내부에 각각 하나씩 있을 때 진입/이탈 카운트를 올리면 된다. #include using namespace std; int main() { int test_num; //Test case 개수 cin >> test_num; while(test_num--){ int x1, y1, x2, y2; int var = 0; //진입, 이탈 몇번 cin >> x1 >> y1 >> x2 >> y2; int n; //행성계 개수 cin >> n;.. 2021. 11. 10.
[백준 1002] 터렛 터렛의 위치와 터렛과 마린사이의 거리가 주어졌다. 터렛의 위치를 원의 중심, 마린은 두 원의 접점이라고 보면 된다. 쉽죠? 근데 처음에는 겹치는 넓이 안에 있는거 다 구해야하는 줄 알았음 ㅋㅋ; 두 원의 위치관계는 중학교 때 배운 것 같은데, 그거 쓰면 된다. 두 원의 중심 사이의 거리를 d, 두 원의 반지름을 각각 r, r' 라고 하면, 요로코롬 된다는 걸 알 수 있다. #include #include using namespace std; typedef long long ll; int main() { int t; cin >> t; for(t; t--; t>0){ ll x1, y1, r1, x2, y2, r2; cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2; ll dx = x1 .. 2021. 11. 8.