Greedy
-
백준 1541번: 잃어버린 괄호 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 24. 23:34
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 접근 괄호를 묶는다는 의미만 알면 쉽게 풀 수 있는 문제다. 다들 알다시피 수학에서 괄호는 '먼저 계산한다'는 뜻이다. 그렇다면 덧셈이 있는 곳에 괄호를 쳐 숫자들을 더해준다면 나중에 뺄 때는 숫자 한 개를 뺄 때보다 훨씬 더 큰 수를 뺄 수 있게 된다. 즉, 가장 작은 수를 만들 수 있다. 구현 또한 간단하다. '-'를 기준으로 나눠준다. 그리고 그 나눠진 문자열을 다시 '+'를 기준으로 ..
-
백준 15729번: 방탈출 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 22. 16:14
https://www.acmicpc.net/problem/15729 15729번: 방탈출 첫째 줄에 N(1 ≤ N ≤ 1,000,000)가 주어지고 둘째 줄에는 쪽지에 적혀 있는 N자리의 수가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 접근 주어진 버튼을 전부 0으로 만들어야 하는 것이 목표다. 또, 누른 버튼의 오른쪽 2개까지 함께 버튼이 눌린다. 이 얘기는 바로 앞 버튼부터 상태가 1인 버튼을 눌러나가야 한다는 뜻이다. 마지막, 혹은 중간부터 누르는 것은 의미가 없다. 그렇게 누르게 된다면 그보다 앞의 버튼을 눌렀을 때 상태가 변하게 될 수 있기 때문이다. 풀이 Python buttonNum = int(input()) board = list(map(int, (input()).spli..
-
백준 16678번: 모독 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 20. 09:00
https://www.acmicpc.net/problem/16678 16678번: 모독 명예에 죽고 명예에 사는 나라 얼라이언스에는 1명의 왕과 N명의 국회의원이 있다. 각 N 명의 국회의원은 a1, a2, ..., aN 의 명예 점수를 갖고 있으며, 명예 점수가 양수인 한 그들은 국회의원을 www.acmicpc.net 접근 연쇄작용이 있다는 것이 중요한 문제. 일단 한 명이라도 명예 점수가 0이 나온 상태가 계속 이어지면 반복해서 국회의원들을 없앨 수 있다. 이 얘기는 무엇이냐, 바로 1부터 가장 큰 수까지 1씩 차이나는 숫자 조합이 만들어져야 한다는 뜻이다. 그래야 -1을 할 때마다 명예점수가 0인 국회의원이 계속 나오고, 한 번의 Defile을 통해 모든 국회의원을 연쇄적으로 없앨 수 있게 된다. ..
-
백준 13164번: 행복 유치원 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 17. 08:46
https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 접근 우선 근처에 있는 원생들의 키 차이를 알아야 한다. 그래야 어떻게 원생 그룹을 나눴을 때, 가장 많은 차이가 나는지 알 수 있기 때문이다. 바로 옆 원생들끼리의 차이를 구해 따로 리스트를 만든다. 이제 해당 리스트들을 오름차순으로 정렬한다. 이때 이 정렬을 기준으로 원생들의 키를 나눌 수 있다. 가장 차이가 많이 나는 원생들을 기준으로 나누는 건 피하고 나머지 원생들을 기준으로 더해준다..
-
백준 12904번: A와 B (Python/Java)Algorithm/Algorithm Problem 2022. 1. 16. 22:47
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 접근 문제 조건을 잘 살펴보면 어렵지 않게 그 힌트를 얻을 수 있다. 한번 연산이 수행될 때마다 글자 맨 뒤에 A가 되었건, B가 되었건 글자가 붙는다. 이 얘기는 한번 연산이 수행될 때마다 무조건 글자 수가 늘어난다는 것이다. 그리고 한번 연산을 할 때마다 뒤에 A 혹은 B가 붙기 때문에 바로 직전에 어떤 연산을 통해 해당 글자가 출력되었는지 확인할 수 있다..
-
백준 16206번: 롤케이크 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 14. 23:23
https://www.acmicpc.net/problem/16206 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 접근 최소 칼질 횟수로 길이가 10인 롤케이크를 최대한 많이 만들기 위해선 10으로 나누어 떨어지는 롤케이크를 잘라야 한다. 예를 들어 확인해보자. 길이가 30인 롤케이크와 35인 롤케이크가 있다고 하자. 길이가 30인 롤케이크는 10 / 10 / 10 두 번의 칼질을 통해 길이 10 롤케이크를 세 개 만들 수 있다. 반면 35인 롤케이크는 10 / 10 / 10 / 5 이렇게 세 번..
-
백준 1092번: 배 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 10. 23:47
https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 접근 굉장히 단순한 문제다. 어렵게 생각할 것 없이, 우선 입력받은 정보를 목록을 만들고 내림차순으로 정렬해준다. 그 뒤, 가장 무거운 무게를 들 수 있는 크레인과 가장 무거운 무게의 박스를 하나씩 확인해보며 걸리는 시간을 구하면 된다. 여기까지는 누구나 쉽게 생각할 수 있는 부분이다. 내가 생각하는 이 문제의 진짜 핵심은 구현 방식이라고 생각한다. while문 속에 for문이, ..
-
백준 1461번: 도서관 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 9. 21:46
https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 접근 처음 풀려고 했던 방식은 가장 거리가 먼 구역을 한 번만 가도록, 즉 가장 마지막에 갈 곳만 생각했다. 그래서 그냥 간단하게 구역을 한 번에 옮길 수 있는 책의 개수로 묶고, 가장 먼 곳을 마지막에 가게끔 구현했다. 하지만 그렇게 풀면 절대 최소 거리가 나올 수 없다는 것은 금방 눈치챌 수 있었다. 예제 1번을 기준으로 생각해보자. 구역을 책의 개수 2개로 나눠보자. 물론 거리가 음수인 구역과 양..