본문 바로가기

문제 해결/BOJ117

[백준] 나눌 수 있는 부분 수열 https://www.acmicpc.net/problem/3673 3673번: 나눌 수 있는 부분 수열 양의 정수로 이루어진 수열이 주어졌을 때, 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오. 예를 들어, 아래와 같은 수열의 부분 수열 중 4로 나누 www.acmicpc.net 누적합을 활용하여 해결할 수 있는 문제입니다. 테케가 200개이고 각 수열은 50000개가 가능하므로 10000000개의 수를 탐색해야해서 빠른 풀이를 찾다가 풀이법을 생각해냈습니다. 구간을 나누었을 때 d로 나누어진다는 것은 누적합들을 구했을 때 나머지가 같은 두 구간을 선택하여 빼주게 되면 d로 나누어지는 구간이 되게 됩니다. 그리고 구간을 선택하지 않고 현재까지 숫자를 모두 더했을.. 2023. 2. 16.
[백준] 계보 복원가 호석 https://www.acmicpc.net/problem/21276 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 어제에 이어서 오늘도 호석님에게 고통받을 뻔 했으나 오늘은 잘 넘겼습니다. 위상 정렬을 사용하여 풀 수 있는 문제입니다. 각 가문의 시조를 찾아서 시조를 시작으로 위상정렬을 수행해주면 됩니다. indegree를 0으로 만드는 조상이 바로 부모이므로 indegree를 0으로 만드는 부모의 자식으로 저장해주면 풀 수 있습니다. import sys from collections import.. 2023. 2. 15.
[백준] 장난감 조립 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 위상정렬과 DP를 함께 수행하는 문제입니다. 골드 2문제라서 그런지 난이도가 꽤 있었습니다. 단순히 위상정렬만 실행을 하면 메모리 초과가 떠서 DP까지 함께 수행을 해줘야합니다. 먼저 기초 부품들을 따로 저장해두고 각 부품별 필요한 기초 부품들을 dp 배열에 저장해둡니다. dp[i][j]는 j를 만들기 위한 i번째 기초 부품의 개수를 저장하고 있습니다. 위상정렬을 해주면.. 2023. 2. 14.
[백준] 문자열 생성 https://www.acmicpc.net/problem/6137 6137번: 문자열 생성 첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N = right: answer += dq.popleft() else: answer += dq.pop() if len(answer) == 80: print(answer) answer = "" cnt += 1 if answer: print(answer, end="") 2023. 2. 14.
[백준] 크게 만들기 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 앞자리에 큰 숫자가 올수록 숫자가 커지게 됩니다. 따라서, 현재 자리수보다 높은 자리수에 있는 숫자가 더 작으면 필요 없는 숫자이므로 버립니다. 만약 그렇지 않으면 유지해줍니다. 버리는 숫자의 개수가 k개가 되거나 더이상 Deque에서 뺄 숫자가 없으면 버리는 행위를 중단합니다. 만약, 숫자가 내림차순으로 정렬되어 미처 버리지 못한 경우가 있을 수 있으므로 k가 남아있는 경우에는 끝에서 k개만큼 버려주면 됩니다. import sys from collections import.. 2023. 2. 13.
[백준] Coins https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net 냅색문제입니다. dp[i][j]를 i번째 동전을 사용하지 않고 j원을 만들 수 있는 경우와 i번째 동전을 사용하여 j원을 만들 수 있는 경우 두가지로 나누어서 생각하면 풀이할 수 있습니다. import sys # sys.stdin = open("input.txt", "r") input = sys.stdin.readline T = int(input()) for _ in rang.. 2023. 2. 13.
[백준] 짝수 팰린드롬 https://www.acmicpc.net/problem/21925 21925번: 짝수 팰린드롬 (1, 1), (5, 6, 7, 7, 6, 5), (5, 5) www.acmicpc.net 반례 찾기가 힘들었던 문제입니다. 스택으로 탐색하면서 짝수 팰린드롬을 만족하는 경우 매칭되는 문자의 인덱스를 저장해둡니다. 단순히 스택만 이용했을 때에는 짝수 팰린 드롬을 만족하지 못하는데에도 정답이라고 나오는 경우가 있습니다. 매칭되는 문자의 인덱스를 저장한 다음 이것을 짝수 팰린드롬을 만족하는지 체크하는데에 사용됩니다. import sys # sys.stdin = open("input.txt", "r") # 숫자의 개수 n = int(input()) # 숫자들 nums = list(map(int, input().sp.. 2023. 2. 13.
[백준] 폴더 정리(small) https://www.acmicpc.net/problem/22860 22860번: 폴더 정리 (small) main 폴더 하위에는 FolderA 폴더 하위에 있는 File1, File2, FolderB 폴더 하위에 있는 File1, File3이 있다. 파일의 종류는 File1, File2, File3 총 3가지이고, 파일의 총 개수는 File1, File2, File1, File3 총 4개이다. mai www.acmicpc.net DFS와 SET을 활용하여 풀 수 있는 문제입니다. 현재 폴더의 하위에 폴더를 만난 경우에는 하위 폴더로 탐색을 시작하게 되고 탐색이 끝나면 하위 폴더들 밑에 있는 파일의 종류와 숫자를 리턴으로 받게 됩니다. 파일의 개수는 더해주고 파일의 종류는 SET이므로 현재 폴더 종류에 .. 2023. 2. 12.
[백준] 탑 보기 https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 스택을 이용하면 풀 수 있는 문제입니다. 빗물문제와 비슷해서 풀이법을 비교적 쉽게 떠올릴 수 있었습니다. 해당 문제를 풀으신 분들은 빗물문제도 도전해보시면 좋을 것 같습니다. 왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽으로 탐색하면서 본인보다 작은 건물들을 스택에서 제거해주면됩니다. 왼쪽 -> 오른쪽을 예시로 설명드리겠습니다. 왼쪽에서 오른쪽으로 탐색하면서 스택에는 빌딩들의 인덱스를 저장하게 됩니다... 2023. 2. 11.

티스토리툴바