https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 2022.07.14 - [Algorithm/BOJ] - [BOJ][python] 11052. 카드 구매하기 문제에서 최대 금액으로 카드를 구매하는 것을 풀었는데, 이번엔 최소 금액으로 구매 해야한다. 풀이 방법은 거의 비슷한데, 최소 금액을 구하기 위해 min_tmp로 최솟값을 갱신하여 카드 i개를 구매하는 비용을 계산한다.초기 min_tmp값은 적당히 큰..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 처음에는 커서를 움직이며 한 배열에서 pop과 insert 연산을 사용했는데, 시간 초과가 발생했다. 쉽게 커서를 구현하려면 스택을 사용하면 된다. 기존 입력받은 배열(arr)과, 커서 뒤의 배열을 위해 스택용(arr_tmp)을 만든다. 커서의 왼쪽은 arr, 오른쪽은 arr_tmp라고 생각하면 편하다. 연산의 종류에 따라 두 배열에 append 및 pop을 통..
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 💡IDEA 집합을 사용하는 문제이다. 쉽고 빠르게 집합을 구현하기 위해 크루스칼 알고리즘을 사용했다. 집합의 부모를 찾는 함수와 합집합 연산을 하는 함수를 만들었다. 연산이 0인 경우에 합집합을, 1인 경우에는 a의 부모와 b의 부모가 같은지 판단하여 출력한다. 📌CODE import sys input = sys.stdin.readline sys.setre..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 가로 세로가 50 이하이므로 브루트 포스를 더불어 사용했다. 육지(L)인 곳 중 상하좌우로 이어진 곳 중 최단 거리로 이동할 수 있어야 한다. 거리를 재기 위해 큐에서 카운트를 세어준다. 반환 값은 계산한 거리 중 가장 큰 값을 반환한다. 모든 행렬을 순환하면서 모든 육지(L)를 확인하며 최단 거리로 이동하는 시간을 갱신하여 출력한다. 📌CODE import s..
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 시작 층(S)에서 시작하여 도착 층(G)까지 U씩 올라가거나 D씩 내려가며 몇 번만에 다다를 수 있는지 판단해야 한다. 버튼을 누르는 횟수는 방문 배열을 사용하여 구하도록 했다. F층 이내에 있는 층 중 방문하지 않은 층을 방문하며 횟수를 세어준다. 도착 층(G)에 다다르면 방문 배열로 센 횟수에서 -1을 해서 출력한다. 첫 시작을 1로 했기 때문에 -1을 해줘야 함을 ..
https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 시작 볼륨에서부터 시작해서 조절할 수 있는 크기만큼 더하고 뺀 값을 바탕으로 dp 배열을 채운다. 예제 입력 1번의 경우는 다음과 같다. S=5에서부터 시작해서 볼륨리스트 첫번째 값인 5를 더하고 뺀 값인 0과 10을 체크해준다. 볼륨리스트 두번째 값은 3인데, 0에서는 3으로, 10에서는 7로 체크할 수 있다. 범..
https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 💡IDEA 수학을 사용하는 문제이다. 1로만 이루어져 있는 수라는 점에서 속을 뻔 했지만, 그냥 상관 없이 두 수의 최대공약수를 구하면 된다. 최대공약수 만큼 1을 연속하여 출력한다. 📌CODE import math A, B = map(int, input().split()) print('1'*math.gcd(A, B))
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 💡IDEA 브루트포스를 사용하는 문제이다. N이 20 이하인 자연수이므로 충분히 브루트포스로 해결할 수 있지 않을까 했다. itertools의 combinations 함수를 사용하여 부분 수열을 구하는데, 조합을 구성하는 개수는 1개부터 N개까지이다. 조합 중 합이 S인 경우에만 개수를 센다. 재귀로도 풀 수 있지만 시간이 훨씬 오래 걸린다. 코드는 두개 모두 ..
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 스택에 차례대로 인덱스와 그 높이를 넣고, 스택의 가장 끝에 있는 값의 높이가 i번째 탑의 높이보다 높은 경우에 결과 배열에 인덱스+1을 저장한다. 높이가 낮은 경우 pop을 해준다. 스택에 아무것도 남지 않을 때까지 반복한 후 다음 인덱스와 높이를 넣는다. 현재 탑을 기준으로 왼쪽, 그러니까 이전의 탑들 중 자신보다 큰 높이의 탑의 인덱스를 저장해야하기 때..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 전깃줄이 겹치지 않기 위해서 A의 전깃줄 순 으로 정렬한 후 A와 연결된 B의 전깃줄 중 가장 긴 증가하는 부분 수열을 구하면 된다. i번째와 i번째 이전까지의 j번째 값을 비교하며 dp 배열을 채운다. i번째 dp 값과 j번째 dp 값에 개수를 하나 더한 값 중 큰 값으로 i번째 dp를 갱신한다. dp의 최댓값은 겹치지 않고 연결된 전깃줄의 개수이므로, 결과..
