본문 바로가기

문제 해결/BOJ117

[백준] 소문난 칠공주 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 완전 탐색 문제입니다. 저는 조합 + 깊이 우선 탐색을 통해 해결하였습니다. 먼저, 좌표의 조합을 구해줍니다. 구해주는 과정에서 도연파가 4명을 넘어가는 경우는 가지치기를 해줍니다. 만약, 칠공주가 완성되면 칠공주가 인접해있는지를 판별해주어야하는데 이를 dfs로 체크해주었습니다. 칠공주가 위치한 곳을 visited[y][x] = true로 만들어주고 dfs로 탐색하면서 false로 바꾸었습니다. 탐색.. 2023. 4. 13.
[백준] 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 그리디 문제입니다. 첫 접근은 빨리 끝나는 강의가 우선순위 큐에서 먼저 나오도록 풀이했습니다. 빨리 끝나는 강의와 겹치는 강의들이 있다면 강의실이 추가적으로 필요하게 됩니다. 만약 겹치지 않는 강의를 만나게 되면 현재 강의가 진행되는데 필요한 강의실의 최대 개수를 갱신시켜주고 해당 강의부터는 이어질 수 있으므로 cnt를 1로 초기화시켜 줍니다. 하지만 이렇게 풀이했을 때의 문제가 있습니다. 6 1 4 4 8 3 5 5 6 6 8 7 8 해당 케.. 2023. 4. 12.
[백준] 동전 분배 https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원 www.acmicpc.net 정말 이 문제가 어떻게 골드3 문제인지 이해가 안되는 문제였습니다. 처음에는 그리디로 접근을 했습니다. 모든 동전의 개수를 짝수로 맞춰주면 된다고 생각을 했고 동전의 가격을 내림차순으로 정렬하여 가격이 큰 동전의 개수를 짝수개로 먼저 맞춰주면서 내려오는 풀이법을 생각했는데 가격의 큰 동전의 가격에 맞게 조합을 짤 경우의 수가 너무 많다고 하여 포기하였습니다. 그래서 알고리즘 분류를 .. 2023. 4. 12.
[백준] LCS3 https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net LCS를 응용하는 문제입니다. 3개의 문자열을 비교해야하므로 3차원 배열을 응용하여 풀이해주면 됩니다. 3개의 문자열의 현재 가르키고 있는 문자들이 같은 경우에는 dp[k][i][j] = dp[k - 1][i - 1][j - 1] + 1 와 같이 되고 문자가 다른 경우에는 3개의 문자열에서 각각 현재 가르키고 있는 문자열을 제외했을 때 얻을 수 있는 LCS 길이 중 최대를 선택해주면 됩니다. dp[k][i][j.. 2023. 4. 11.
[백준] 소풍 https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 풀이법이 잘 생각나지 않아서 알고리즘 분류를 확인하고 푼 문제입니다. 딱히 떠오르는 풀이법이 없어서 완탐이나 백트래킹으로 접근해야하는 것은 알고 있었는데 시간초과가 나지는 않을까 생각이 들어 쉽게 시작하지 못했습니다. 특히, 백트래킹의 경우에는 시간복잡도를 예측하기가 쉽지 않은 것 같습니다. 풀이법은 간단합니다. 현재 학생과 친구여야만 하는 목록들을 넘겨주고 이를 만족하지 못하면 같이 소풍을 갈 수 없.. 2023. 4. 10.
[백준] 팰린드롬 만들기 https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 오늘은 ㅅㅈ코테로 인해 심신이 지쳐서 쉬어가는 문제로 해당 문제를 택해보았습니다. 팰린드롬 문제입니다. 문제를 제대로 읽었어야했는데 문자열의 앞으로는 문자들을 추가할 수 없고 뒤로만 문자를 추가할 수 있다는 조건이 있습니다. 풀이법은 현재 위치의 문자가 팰린드롬의 중앙이라고 생각했을 때 뒤로 문자를 얼마나 추가해야 팰린드롬이 되는지 체크해주면 됩니다. 만약, 현재와 다음 문자가 같다면 두 문자를 중심으.. 2023. 4. 9.
[백준] 원자의 에너지 https://www.acmicpc.net/problem/2058 2058번: 원자의 에너지 잘 알려져 있듯, 각각의 원자들은 어떤 특정한 에너지 상태(혹은 에너지 준위)에 놓일 수 있다. 각각의 상태는 그 상태에서 그 원자가 갖는 에너지로 나타낼 수 있다. 어떤 원자가 높은 에너지 상 www.acmicpc.net 문제 해석이 어려웠던 문제입니다. 질문 게시판의 지문 해석 글을 보지 않았다면 풀기가 힘들었을 문제입니다. 문제 이해 자체가 어려웠다면 해당 글을 참고해보시면 좋을 것 같습니다. 결국, 원소의 상태간의 경로가 유일하게 존재한다는 의미는 원소의 상태를 그래프로 그리면 트리가 된다는 것을 의미합니다. 트리를 구축하기 위해서는 양성자를 더하거나 뺐을 때 원소의 상태로 존재할 수 있으면 간선이 있다는.. 2023. 4. 9.
[백준] 순회강연 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 정렬과 우선순위 큐를 활용한 그리디 문제입니다. 각 날짜별로 페이를 집어넣은 다음 페이가 큰 순서로 내림차순으로 정렬해줍니다. 다음으로 날짜순으로 탐색을 시작합니다. 우선순위 큐의 역할은 현재 날짜까지 받은 페이중 가장 작은 값이 먼저 나오도록 하는 min heap입니다. 큐의 크기는 현재 날짜와 최대한 일치하도록 해야합니다. 예를 들어 현재가 10일이면 10일.. 2023. 4. 8.
[백준] 두 배열의 합 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 누적합을 활용하여 풀이하였습니다. 누적합을 사용한 이유는 A와 B 배열 각각의 구간 합을 알아야하기 때문입니다. 먼저, A에 대해 누적합을 하면서 모든 구간의 합을 a_prefix에 저장해둡니다. 그 다음 B의 모든 구간합을 구하면서 a_prefix에 저장되어 있는 값과 현재 구간합의 합이 T를 만족하면 정답이 되게 .. 2023. 4. 7.

티스토리툴바