두부의 코딩일기

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net ✅ 골드 Ⅲ 🔶 풀이 알고리즘 분류에는 자료 구조, 정렬, 우선순위 큐라고 적혀있는데 다 필요 없다. 그냥 그리디 알고리즘으로 해결할 수 있다. 마감일까지 남은 일수와 과제 점수 두 개를 입력받을 때 마감 기한 중에 가장 긴 날짜를 구한 후에 거꾸로 계산하면 된다. 예제에서는 가장 길게 남은 마감 기한은 6일이므로 6일차부터 1일차로 순서대로 내려가면 된다. 6일차: 점수 5점짜리 과제만 있음. 5일차: 과제 없음 4일차: 60, 40, 1..

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net ✅ 실버 Ⅴ 🔶 풀이 편의점 카운터에서 일한다. 2원과 5원만 이용해서 최소한의 동전으로 거스름돈을 주면 된다. 해당 문제에 알고리즘 분류는 dp, 그리드 알고리즘 두 가지 방법으로 다 풀어봤다. 1️⃣ dp Bottom-Up 방법을 사용. 우리가 알 수 있는 작은 문제는 5원까지. 1원 = X 2원 = 1개 3원 = X 4원 = 2개 5원 = 1 6원부터 시작하면 시작하면 된다. dp[6] = Math.min(dp[6-2], dp[6-5]) → Math.min(dp[4], dp[1]) → 2 와 Integer.MA..

https://www.acmicpc.net/problem/15736 15736번: 청기 백기 예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된 www.acmicpc.net ✅ 실버 Ⅳ 🔶 풀이 완전 탐색으로 풀면 범위가 너무 넓어서 시간 초과가 발생한다. 규칙을 찾아서 해결해줘야되는 문제. 1은 약수가 1개, 한 번 뒤집힘 2는 약수가 2개, 두 번 뒤집힘 = 그대로 청색 4는 약수가 3개, 세 번 뒤집힘 6은 약수가 4개, 네 번 뒤집힘 = 그대로 청색 9는 약수가 3개, 세 번 뒤집힘 루트 N이 정수일 때만 백기 상태로 뒤집히는 것을 알 수 있다. 따..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 임의의 버튼이 고장났을 경우 채널 N으로 이동하기 위해서 눌러야하는 버튼의 최소값. 완전탐색 브루트포스 문제. 1️⃣ 지금 보고 있는 채널은 100번 2️⃣ 고장난 버튼이 없을 수도 있다. 3️⃣ 완전탐색의 범위는 0 - 999,999 필자는 주로 StringTokenizer을 사용하는데 2️⃣번 예외에서 고장난 버튼이 0개면 Null Point 에러가 발생한..

https://www.acmicpc.net/problem/5107 5107번: 마니또 N명의 사람들이 있다. 이들은 각자 다른 한 명의 이름이 적힌 쪽지를 받아서, 그 사람에게 몰래 선행을 베푼다. 이때 자기 자신의 이름을 받을 수는 없으며, 선행을 받은 사람은 누가 자신을 도와 www.acmicpc.net ✅ 실버Ⅰ 🔶 풀이 A에서 출발해서 B, C, ··· 를 지나서 다시 A로 돌아오는 경우가 몇 개나 발생하는가. 1️⃣ 선행을 베푸는 사람과 선행을 받는 사람은 결코 중복되지 않는다. 2️⃣ 이름의 길이는 10글자가 넘지 않고 테스트 케이스마다 사람은 3명에서 20명이다. 해당 문제에서는 딱히 신경써야할 조건은 없다. 1️⃣번 조건을 봤을 때 HashMap을 사용하면 될 것 같다고 생각했다. Hash..

https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net ✅ 골드 Ⅳ 🔶 풀이 N x M 크기의 고급 나무 재료가 주어졌을 때, 'ㄱ'자 모양 부메랑들의 강도 합이 최댓값을 구하라. N과 M의 크기가 작으므로 완전 탐색으로 해결할 수 있다. 우선 백트래킹을 사용하기 위해서 dfs를 이용한다. idx를 0부터 순차적으로 늘리면서 좌표값 (x, y)를 제어해 줬다. int x = idx/M; int y = idx%M; idx가 N*M에 도..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 해당 문제는 완전 탐색으로 진행하면 시간 초과가 발생한다. 때문에 정렬과 우선순위 큐를 이용해서 해결할 수 있다. 위 그림은 예제 1번을 보기 좋게 표현했다. 수업이 끝난 직후에 다음 수업을 시작할 수 있다고 했으므로 강의실 2개를 사용한다. 우선, 시작 시간을 기준으로 오름차순 정렬을 해줘야된다. 마감 시간을 기준으로 오름차순 정렬하게 되면 아래와 같은 상황에서 반례가 발생한다. 4 1 2 1 4 2 6 4 5 1. (1..

https://www.acmicpc.net/problem/25379 25379번: 피하자 음이 아닌 정수로 이루어진 길이 N의 배열 A = [A1, A2, · · · , AN]가 있다. 배열 A에서 인접한 두 수를 교환하는 시행을 원하는 만큼 할 수 있다. 이 때, 홀수와 짝수가 인접한 경우가 최대 1번 등장 www.acmicpc.net 🔶 풀이 알고리즘은 정말 둘 중 하나다. 엄청 잘 풀리거나 끝까지 막히거나..😭 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 만들어라. 즉, 모든 짝수 혹은 홀수를 왼쪽 혹은 오른쪽으로 이동시켜라. 필자는 짝수를 선택해서 왼쪽 혹은 오른쪽 끝으로 이동시켰다. i번째 정수가 짝수라고 가정했을 때, 왼쪽 끝으로 이동할 경우에는 i, 오른쪽 끝으로 이동할 경우에는 N -..

https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net · · · (이하 생략) 🔶 풀이 필자는 해당 문제를 아래와 같은 순서대로 풀었다. 1. 박스 정보를 가까운 순으로 정렬하기. : 거리가 먼 박스를 싣고 이동하면 중간에 옮길 수 있는 상자를 놓칠 수 있다. 따라서, 받는 마을이 가까운 순으로 정렬해 주고, 보내는 마을을 가까운 순으로 정렬해 주면 된다. public static class Box implements Compar..

https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 🔶 풀이 11명 선수의 포지션 별 능력이 입력된다. 포지션 별로 중복되지 않은 선수 11명을 뽑아서 최대 점수를 구하라. 완전 탐색으로 진행하게 되면 경우의 수는 11! (39,916,800)로 시간 초과가 발생할 수 있다. 때문에 백트래킹을 사용해서 시간 복잡도를 줄여야한다. 위 문제에서 능력치가 0인 경우에는 해당 포지션에 설 수 없다고 했다. 또한, 이미 선발된 선수가 또 다시 선발될 수 없으므로 selected[] 배..