🔗 문제 링크 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 💡 문제 풀이 및 해석 블루레이의 사이즈는 최대 10억이다. 따라서 최대 크기를 10억으로 잡아두고 시작한다. 블루레이의 사이즈를 이분탐색으로 정한다. 블루레이에 담기는 순서는 강의의 순서와 같으므로, 순서대로 블루레이에 강의를 담는다. 그렇게 블루레이가 꽉 차면 다음 블루레이에 담기는 순서로 이분탐색을 진행하면 된다. ⭐️ 정답 코드 및 설명 #include #include using namespace std; int N, M; vector lectur..
baekjoon
🔗 문제 링크 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 💡 문제 풀이 및 해석 치킨집은 13개 이하, 그냥 집은 최대 2N 이다. 조합으로 13개를 뽑는다면, 최대 13C6 이다. 따라서 1716 * 2 * 50 이므로 브루트포스하게 풀 수 있다. 이제 치킨집을 고른 뒤, 집마다 치킨집까지의 거리를 구하고 가장 가까운 거리를 계속 더해주면 된다. ⭐️ 정답 코드 및 설명 #include #include #define INF 987654321 using namespace std; in..
🔗 문제 링크 https://www.acmicpc.net/problem/9251 💡 문제 풀이 및 해석 '최장 부분 공통 수열' 문제는 DP를 사용한다. 어떻게 풀지 모르겠어서 구글링을 하여 아래 사이트에서 이해를 한뒤 풀었다. 주석을 풀면 myMap이 만들어진 것을 볼 수 있다. 도움을 받은 사이트 ⭐️ 정답 코드 및 설명 #include #include using namespace std; string str1, str2; //string answer = ""; int myMap[1001][1001]; void input() { cin >> str1 >> str2; } int sol() { for (int y = 1; y
🔗 문제 링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 💡 문제 풀이 및 해석 만약 카드의 숫자가 N개라면 반드시 N-1번의 계산을 해야 한다. 여기서 가장 적은 수를 더해야 한다. 항상 가장 작은 두 집합을 더해준다. 이러면 결과적으로 가장 작은 수가 나온다. 만약, 큰 수가 들어가게 된다면, 그 수는 총 연산에서 이번 연산을 제외하고 반드시 한번 더 들어가야 하므로 최소값이 될 수 없다. ⭐️ 정답 코드 및 설명 #include #include using namespace std; i..
🔗 문제 링크 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 💡 문제 풀이 및 해석 주어진 단어중 정해진 갯수를 뽑는 조합문제이다. 조합으로 뽑은 다음에, 모음이 1개 이상, 자음이 2개 이상 들어갔는지 체크해주면 됩니다. ⭐️ 정답 코드 및 설명 #include #include #include #include using namespace std; int L, C; bool visit[15]; vector word; set answer; void input() { cin >> L >> C; word = vecto..
🔗 문제 링크 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 💡 문제 풀이 및 해석 원형이 PPAP 인지 확인해야 하는 문제다. P -> PPAP 이므로 역으로 생각하면 PPAP -> P 가 된다고 생각할 수 있다. 그럼 문자열에서 앞에서부터 PPAP 인 부분을 P 로 바꿔가면서 O(N) 으로 탐색하면 된다. ⭐️ 정답 코드 및 설명 #include #include using namespace std; string sol(string str) { string temp = ""; int tempIndex = 0; for (int i = 0; i < str.siz..
🔗 문제 링크 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 💡 문제 풀이 및 해석 주어진 조건이 뒤에 'A'를 붙이는 것과 'B'를 붙이고 뒤집는 것이다. 최악의 조건을 생각해보자. S.size() = 1, T.size() = 50 이다. 여기서 S -> T 로 갈 때, 브루트포스하게 할 수 없다. 2의 50제곱은 좀 많이 크다. S -> T 로 갈 때, 조건을 설정해주면 어떨까?? 이 문제는 사실 ..
🔗 문제 링크 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 💡 문제 풀이 및 해석 문제부터 선수과목이라고 써져 있는 것을 보니, 위상정렬 문제임을 알 수 있다. (많이 풀어본 경험으로써??) 위상정렬이라고 마냥 어렵게 생각할 것 없다. 과목 A를 해결하면 과목 B를 배울 수 있다는 조건을 보자. A -> B 라고 생각하자. 그러면 화살표를 받는 B는 선수과목의 숫자가 +1이 되는 것이다. 그러면, 이는 선수과목의 숫자가 0이라면 수강할 수 있다는 뜻이 되기도 한다. 3번 해석을 input()에 적용시켰다. X가 선수과목해야 하는 숫자..
