목록전체 글 (124)
풀이 보관함
🔗 문제 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 일 때 스왑한 후 확인하는게 원인일까 싶어 스왑 전에 첫번째 자리..
memset() https://en.cppreference.com/w/cpp/string/byte/memset std::memset - cppreference.com Copies the value static_cast (ch) into each of the first count characters of the object pointed to by dest. If the object is a potentially-overlapping subobject or is not TriviallyCopyable (e.g., scalar, C-compatible struct, or an array of trivially copyab en.cppreference.com - 메모리 변화가 있는건 fill() 권유 하고 있..