Algorithm/Algorithm Problem
-
백준 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..
-
백준 3079번: 입국심사 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 21. 09:05
https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 접근 이분 탐색은 결국 정렬되어 있는 범위 혹은 배열을 반씩 나누어 탐색하는 방법이다. 즉, 범위의 최솟값과 최댓값을 아는 것이 중요하다. 해당 문제에서 가장 최소로 나올 수 있는 시간 값은 가장 짧은 심사 시간이다. 최대로 나올 수 있는 시간은 가장 긴 심사시간에 모든 친구들이 심사를 받았을 때, 즉 '가장 긴 심사시간*친구 수'다. 이 범위를 중심으로 이분 탐색을 해본다. 설정한..
-
백준 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을 통해 모든 국회의원을 연쇄적으로 없앨 수 있게 된다. ..
-
백준 16564번: 히오스 프로게이머 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 19. 21:35
https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net 접근 이분 탐색 문제를 풀 때 제일 먼저 찾아야 하는 조건은 최솟값과 최댓값이다. 이분 탐색은 특정 정렬 혹은 범위를 반씩 나눠가며 탐색하는 알고리즘이다. 때문에 범위를 특정할 수 있는 최솟값과 최댓값을 구하는 것이 필수적이다. 예시를 통해 살펴보자. 여기서 구할 수 있는 최솟값은 당연하게도 가장 낮은 레벨인 10이다. 그..
-
백준 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가 붙기 때문에 바로 직전에 어떤 연산을 통해 해당 글자가 출력되었는지 확인할 수 있다..
-
백준 3055번: 탈출 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 15. 17:11
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 접근 문제 설정이나 출력 예시만 조금 다를 뿐, 백준 5427번 불(https://www.acmicpc.net/problem/5427)과 아예 똑같은 문제다. 백준 5427번 풀이를 작성한 적이 있으니(https://codestation.tistory.com/14) 참고하면 될 것이다. 풀이 Python from collections import deque upDown = [-1, 1, 0, 0] leftRi..
-
백준 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 이렇게 세 번..