문제https://www.acmicpc.net/problem/29704문제 설명N개의 문제와 제출기한 T일이 주어지고, 각 문제 별 소요되는 일 수와 벌금이 주어진다.제출기한 T일이 지났을 때 내는 벌금의 총금액이 최소가 되도록 하려고 한다. 풀이문제를 보고 배낭 알고리즘이 생각났다.배낭문제는 N개의 아이템이 존재할 때 총 W의 무게를 넘기지 않으면서 가치의 합이 최대가 되도록 하는 문제이다. 이 문제의 차이점은 가치의 합이 최대가 아니라 최소가 되어야 한다는 것이다. 하지만 알고리즘의 큰 틀은 벗어나지 않기 때문에 빠르게 2차원 표를 만들어서 검증한 후 점화식을 세웠다. 문제에 나와있는 1번 예제를 통해 답을 검증했다.3 32 50001 10001 2000 0번 문제금액 / 일0123 ..

문제https://www.acmicpc.net/problem/1912문제 설명 N개의 정수로 이루어진 임의의 수열이 주어진다.이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.단 수는 1개 이상 선택한다. 풀이두 개의 반복문을 이용해서 현재 위치기준 이전 값들을 더해가며 최댓값을 갱신하면 답을 구할 수 있다.하지만 이 방법은 $N^2$의 시간복잡도를 요구하기 때문에 $N = 10^5$인 이 문제에서는 적합하지 않다. 따라서 $O(N)$으로 해결할 수 있는 방법을 생각했다. 이 문제에서는 연속된 수를 선택한다는 것이 핵심이다.내가 현재 특정 원소에 있을 때 선택할 수 있는 경우는 두 가지이다. 1. 이전에 연속된 수에서 최댓값이 나올 수 있을 때 이전 + 현재 원소를..

문제https://www.acmicpc.net/problem/23560문제 설명백준이는 N일 동안 약을 먹어야 한다.약은 아침, 점심 저녁에 한 번씩 먹어야 하고, 한 번먹은 약은 약 봉투에 담겨있다.약 봉투는 3N개가 일렬롤 붙어있다.(아침, 점심, 저녁)을 N번 이어붙인 형태로.약을 먹을 땐 가장 앞에있는 약 봉투와 가장 뒤에 있는 약 봉투만 뜯어서 먹을 수 있다.아침, 저녁은 같은 약이기 때문에 상관없이 먹어도 된다.점심약은 점심에만 먹어야 한다.N이 주어질 때 약을 먹는 서로 다른 방법의 수를 구해보자. 풀이나는 이 문제가 이해가 잘 안가서 N = 1 ~ 3까지 전부 구했다.N = 1, 2가지N = 2, 6가지N = 3, 18가지... 으로 나오길래 이전 항의 3배를 해서 다음항을 구했더니 정답이..

문제https://www.acmicpc.net/problem/10216문제 설명2차원 평면 위에 N곳에 적군의 진영이 설치되어 있다.각 진영마다 1개의 통신탑을 놓는다. $i$번째 적군의 통신탑은 설치 위치로부터 $R_i$ 이내 거리에 포함되는 모든 지역을 자신의 통신영역 $A_i$로 가지게 된다.만약 $A_i$와 $A_j$가 닿거나 겹치는 부분이 있다면 두 진영 i와 j는 직접적으로 통신이 가능하다.두 진영이 직접적으로 통신이 불가능 하더라도 다른 진영들을 거쳐 통신이 가능하다면 최종적으로 통신이 가능한 것으로 본다.이러한 통신망의 개수가 몇 개인지 구한다. 풀이문제가 너무 복잡하다. 예제 1번을 통해 그림으로 문제를 이해해보자. 2개의 적 진영이 주어졌다. 이를 그림으로 표현해보자.1. (0,0), ..

문제https://www.acmicpc.net/problem/12014문제 설명N일간 총 N개의 주식 가격이 숫자로 주어진다.총 K번의 주식을 구매하려고 한다.주식은 하루에 한 번만 살 수 있다.맨 처음을 제외하고는 바로 직전에 주식을 샀을 때보다 가격이 올라갔을 때만 사야 한다.N과 K가 주어졌을 때, 조건에 만족하게 주식을 구매할 수 있는지 여부를 출력한다. 풀이총 N개의 데이터가 수열로 주어진다.N개 중 연속으로 증가하는 K개의 숫자가 존재하는지 문제는 묻고있다. N개중 K개가 증가하는지 확인하려면 매 원소마다 현재 내 앞에 나보다 작은 숫자가 몇개있는지 검사해야 한다. 이를 최장 증가 부분 수열(LIS) 알고리즘이라고 부른다.LIS 알고리즘은 단순히 $N^2$으로 구현하는 방식이 있고, 이분탐색을..

문제https://www.acmicpc.net/problem/2176문제 설명그래프의 한 정점 S에서 다른 한 정점 T로 이동하려 한다.이동할 때 T로 가까워지며 이동하는 경우, 이를 합리적인 이동경로라고 한다.합리적인 이동 경로는 최단경로가 아닐 수 있다.그래프가 주어질 때 합리적인 이동경로의 개수를 구하라.이 때 S = 1, T = 2이다. 풀이합리적인 이동경로라는 말이 정말 이해가 가지 않았다. 따라서 그림을 그려가며 이해했다. 다음과 같은 그래프가 존재할 때 합리적인 이동경로를 생각해보자. 1에서 2로 갈 수 있는 경로는 총 2개이며, 최단거리는 3이다.1 -> 3 -> 2 (dist = 3)1 -> 4 -> 2 (dist = 5) 합리적인 이동경로란, 매 이동을 할 때마다 1에서 2까지의 거리가..

문제https://www.acmicpc.net/problem/9047문제 설명Kaprekar 연산이란, 네 자리수 중 모든 자리가 같지 않은 수(1111,2222 등 제외)의 각 자리를 재배열해서 만들 수 있는 가장 큰 수와 가장 작은 수를 만들어서 그 차이를 계산한다.위 연산을 반복했을 때 매번 6174를 만들어낸다.숫자가 주어졌을 때 6174로 몇 번만의 연산으로 갈 수 있는지 계산한다. 풀이카프리카 상수 6174는 어떤 4자리 숫자를 대입해도 최대 7번의 연산으로 도달이 가능하다고 한다.따라서 단순히 숫자를 입력받고 이를 오름차순, 내림차순 정렬하여 다음 숫자를 구하는 과정을 반복했다. 문자열 s를 오름차순, 내림차순 정렬하여 두 수를 구한다.두 수를 연산하여, 다음 수를 구한다.이 때 4자..

문제https://www.acmicpc.net/problem/15973문제 설명 2차원 좌표 평면 위에 두 개의 박스 P,Q가 놓여 있다.각 박스의변은 x 혹은 y축에 평행하다.두 박스가 서로 교차하는지 여부를 판단하고 싶다.내부가 겹쳐있다면 FACE선분에서 만난다면 LINE한 점에서 만난다면 POINT만나지 않는다면 NULL두 박스의 좌표가 주어질 때 교차 여부를 판단한다. 풀이두 박스의 내부가 겹쳐있는 것을 판단하려면, 임의의 두 좌표가 동일하게 존재해야 한다. 하지만 이를 확인하려면 모든 좌표를 검사해야하는데, 문제에서 주어진 좌표의 범위는 $-10^9$에서 $10^9$이기 때문에 모든 범위 내 모든 좌표를 검사하기 어렵다. 따라서 나는 FACE인 조건을 찾기보다는 상대적으로 찾기 쉬운 다른..

문제https://www.acmicpc.net/problem/13265문제 설명여러 동그라미와 동그라미 두 개를 연결하는 직선들 만으로 그림을 그린다.연결된 두 동그라미는 서로 색이 다르게 되도록 색을 칠하고자 한다.이 동그라미들이 서로 연결된 직선에 대한 정보가 주어졌을 때, 2가지 색상으로 색칠이 가능한지 확인한다. 풀이이 문제는 동그라미들이 하나로 연결되어 있는 것이 아니라, 여러 개의 트리로 구성되어 있을 수 있다.따라서 노드를 완전탐색하면서 방문되지 않은 노드에서 bfs를 진행하며 2가지 색상으로 구성이 가능한지 탐색한다. 모든 노드를 탐색하며 BFS를 진행한다.각 노드를 탐색하며 부모가 0이면 자식은 1, 부모가 0이면 자식은 1로 갱신하며 BFS 탐색을 진행한다.만약 부모와 자식이 같은..

문제https://www.acmicpc.net/problem/19622문제 설명N개의 회의와 하나의 회의실이 존재한다.각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고, 동시에 두 개 이상의 회의가 진행될 수 없다.회의는 도중에 중단될 수 없으며, 한 회의가 끝나는 동시에 다음 회의가 시작될 수 있다.회의는 다음과 같은 조건을 만족한다.임의의 회의 K는 K-1과 K+1과 회의 시간이 겹치고 나머지와는 겹치지 않는다.모든 회의의 시작 시간과 끝나는 시간은 서로 다르다.N개의 회의를 효율적으로 배정할 경우 회의를 진행할 수 있는 최대 인원을 구한다. 풀이이 문제의 핵심은 임의의 회의 K는 K-1과 K+1과 회의 시간이 겹치고 나머지와는 겹치지 않는다. 조건에 있다고 생각한다. 1..