problem solving

🔗 문제 17509번: And the Winner Is... Ourselves! 17509번: And the Winner Is... Ourselves! 11 lines are given as the input. The $i$-th line contains two space-separated integers, $D_i$ and $V_i$, where $D_i$ is the amount of minutes required to solve the $i$-th problem, and $V_i$ is the number of incorrect verdicts on the $i$-th problem. For eac www.acmicpc.net 🖍 풀이 총 11 문제를 풀 것이다. 모든 문제를 풀 수 있는 문제들이며..

🔗 문제 1493번: 박스 채우기 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 🖍 풀이 ✔️ 최적의 해 구하는 방법 크기가 큰 큐브부터 넣는다. 크기가 큰 큐브부터 넣는건 바로 떠올릴 수 있지만, 이 문제는 큐브를 넣었을 때 크기가 다른 박스가 3개 생긴다는 유념해야 한다. 말이 쉽지.. 소스짜기 힘들어서 다른 사람 소스를 참고 했다. https://yeeybook.tistory.com/95 [백준] 1493번 박스 채우기 1493번: 박스 채우기 세준이는 length ×..

🔗 문제 13904번: 과제 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 🖍 풀이 ✔️ 최적의 해 구하는 방법 과제 점수가 높은 걸 챙기되, 최대한 마감일에 내면 된다. 과제 점수가 높다고 첫날부터 해버리면 안된다. 1 30, 5 100 일때를 생각해보자. 130점을 챙길 수 있는데 100점만 맞을 수도 있다. 또 하루에 한 과제만 할 수 있으니 visited[i]로 i 날 과제를 냈는지 안 냈는지 확인해줘야 한다. + 천재같은 사람을 봤다.. 입력을 {-d, w} 받으면 비교 함수를 안 만들어도 된다. 💾 소스 #include #include #in..

🔗 문제 https://www.acmicpc.net/problem/15748 15748번: Rest Stops The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest st www.acmicpc.net 🖍 풀이 * 이 문제 전에 boj 회의실 배정, 강의실 배정을 순서대로 푸는 걸 권장한다. 당연히 가치가 큰 휴식..

🔗 문제 11000번: 강의실 배정 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 🖍 풀이 ✔️ 최적의 해 구하는 방법 한 강의실에 최대한 많은 강의를 해야 한다. 강의 시간이 담긴 벡터를 정렬하는 이유 시작 시각 정렬을 하면 한 강의실을 쓸 수 있는지 연속해서 판단이 가능하기 때문이다. 우선 순위 큐를 사용하는 이유 아래 예시는 (1, 7), (7, 10)과 (2,3), (3, 4), (4, 8) 강의를 묶어 최소 2개의 강의실을 사용할 수 있다. 5 1 7 2 3 3 4 4 8 7 10 (1, 7), (2, 3)이 같은 강의실은 같은 강의실을 못 쓴다는..

🔗 문제 1931번: 회의실 배정 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 🖍 풀이 ✔️ 최적의 해를 구하는 방법 회의가 끝나는 시각으로 정렬한 후, 다음 회의 시작 시각보다 같거나 큰 회의를 잡는다. 회의가 언제 시작했던 빨리 끝내야 뒤에 시간이 많다는걸 생각해내면 된다. 시작 시각으로 정렬한 후 가능한 회의 개수는 3개 (오답) 종료 시각으로 정렬한 후 가능한 회의 개수는 4개 (정답) 시작 시각과 끝나는 시각을 std::pair로 저장했다. 종료 시각이 같다면 시작 시각이 빠른 걸로 선택할 수 있도록 정렬하기 위해 비교 함수를 커스텀해줘야 한다. bool compare(const std::pair& a, cons..

🔗 문제 https://www.acmicpc.net/problem/1449 🖍 풀이 HTML 삽입 미리보기할 수 없는 소스 [i번째 구멍 ~ 최대 j 구멍까지 거리] + [여유 거리 (1)]이 테이프 길이를 초과한다면? 그 바로 직전까지 i ~ j-1 는 한 테이프로 막을 수 있다. 먼저 입력이 오름차순이 아닐 수 있기에 구멍난 위치들을 정렬한다. #include ... std::sort(pipe, pipe+N); 그 후에 생각했던 가설을 코드로 옮겼다. for(int i=0; i= L)문으로 변경 💾 소스 #include #include #define MAX 10001 int main() { int N, L; int tape = 0; int pipe[MAX]; //input std::cin >> N >..

🔗 문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 🖍 풀이 뭔 소리인가 이해하는데 3분 더 걸린 문제 10, 15 로프를 예를 들자면 10 줄은 10 중량을 15 중량을 15 중량을 감당할 수 있다. 10과 15. 두 줄을 쓴다고 25 중량은 불가하다. 왜냐하면 10줄은 10까지 밖에 견딜 수 없기 때문이다. 그래서 두 줄을 모두 사용한다면 [가장 작은 10줄*사용줄 수] 값인 20이 정답이다. 💾 소스 #include #inc..

🔗문제 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 🖍풀이 메모리초과와 시간초과를 많이 봤다. 같은 로직으로 파이썬으로 제출했더니 맞았습니다 라서 더 힘들었다. (내 로직이 잘못되지 않았다는 믿음 → 로직 변경할 생각 x) 자릿수가 길어질 때 std::stoi나 std::to_string이 느린건가 싶어 별 짓 다 해봤다. 그래서 변환 없이 std::string끼리 비교하게 바꿨다. (비교대상이 둘 다 숫자라 오류는 안 났음) 첫번째 자리수가 0 일 때 스왑한 후 확인하는게 원인일까 싶어 스왑 전에 첫번째 자리..

🔗문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 🖍풀이 std::queue water; std::queue S; std::pair D; // 비버의 소굴은 이동하지 않는다. 입력을 받으면서 필요한 좌표들을 미리 저장한다. 필요한 좌표를 찾기 위해 이차원 함수를 탐색하고 싶지 않기 때문이다. 이동이 필요한 물과 도치를 BFS 탐색을 위해 queue에 저장한다. void BFS(std::queue& q, const bool isWater, bool& f..