순간을 성실히, 화려함보단 꾸준함을

www.acmicpc.net/problem/2651 2651번: 자동차경주대회 전국 자동차 경주 대회가 매년 열리고 있다. 이 대회에서는 출발지점부터 도착지점까지 거리가 워낙 멀기 때문에 경주 도중에 각 자동차는 정비소를 방문하여 정비를 받아야 한다. 정비소들은 www.acmicpc.net 문제 : 도착지점까지 정비소에 들려 최소의 시간으로 도착할 수 있는 케이스를 구해라 풀이 : LIS의 응용버전 1)각 정비소간 거리를 prefix 로 담아준다. 2)O(n^2)의 시간복잡도를 활용하여 정비소간 차이가 D(정비소에 들렸을때 최대로 갈 수 있는 거리) 이하이고 시간이 더 적게 걸릴때 업데이트, 또한 지금까지 거쳐온 정비소의 번호를 기록해 둔다. 3)지나온 자취를 역추적 + 데이터 추가로 코드 수정(int-..

www.acmicpc.net/problem/2020 2020번: 부분 염기서열 길이 n(1≤n≤1,000)인 염기서열이 있다. 이는 A, G, C, T로 구성되어 있는 문자열이라 생각할 수 있다. 주어진 염기서열의 부분 염기서열은, 염기서열을 문자열로 생각했을 때 부분문자열과 같이 정 www.acmicpc.net 문제 : 문자열이 주어지고 동일한 부분 문자열의 빈도가 m 이상일때 조건에 맞게 정렬해라. 그리고 k 번째 문자열을 출력해라. 해설: 너무 어려움,,,혼자 힘으로 못풀었습니다.(메모리 제한 때문에 ㅠㅠ) 해결 과정은 BFS를 푸는 것 처럼 풀 수 있습니다. 1)입력 문자열(str)의 각 문자를 동일한 문자끼리 모읍니다.(map) 2)그리고 나서 큐를 선언하고 vector를 push 해줍니다. 3..

codeforces.com/contest/1428/problem/C Problem - C - Codeforces codeforces.com 문제 : 문자열이 주어지고 문자열중 'AB'와 'BB'가 존재한다면 증발한다. 이 작업을 반복하여 실행할 때 문자열을 최소로 만들어서 길이를 구하는 문제이다. //참고로 백준문제 : 문자열 폭발 과 동일한 문제이다. 해설 : stack을 이용하면 된다. 하나씩 넣고 조건에 맞는 문자열이라면 pop 해주는 식으로. #include using namespace std; using ll = long long; int arr[2][300010]; void solve(); int main() { ios::sync_with_stdio(false); cin.tie(0); int ..

codeforces.com/contest/1428/problem/B Problem - B - Codeforces codeforces.com 문제 : n개의 간선의 정보가 주어진다. - : 양옆으로 갈 수 있는 간선 > : i 에서 (i+1)%n 으로 갈 수 있는 간선 ) 만으로 이루어져 있거나 (-,> t; while (t--) solv..

codeforces.com/contest/1428/problem/A Problem - A - Codeforces codeforces.com 문제 : 쥐가 상자를 끌고 다닌다. 이때 항상 쥐는 상자의 인접한 위치에만 있을 수 있고 상자를 끌을 수 있다. 쥐는 1단위로 움직일 수 있다. 이때 상자의 초기 위치(x1,y1)이 주어지고 이를 목적 위치(x2,y2)에 옮기기 위해 최소로 움직이는 횟수를 구하면 된다. 예시) (1,1) - > (2,2) 로 옮긴다고 해보자 1) 상자 (1,1) , 쥐(2,1) //init 2) 상자(2,1) , 쥐(3,1) 3) 상자(2,1) , 쥐(3,2) 4) 상자(2,1) , 쥐(2,2) 5) 상자(2,2) , 쥐(3,2) //end 그러면 4번의 움직임에 원하는 위치에 상자..

codeforces.com/contest/1427/problem/B Problem - B - Codeforces codeforces.com 문제 : 문자열 s가 주어지고 W는 이김,L는 진거다. 이때 연속적으로 이긴다면 +2포인트를 얻고, 진다면 +0포인트를 얻는다. 또한, 연속된 W의 문자열 중에 제일 첫번째 W는 +1 포인트만 얻는다. 그리고 m번만큼 L->W로 바꿀 수 있다. 이때 최대로 얻을 수 있는 점수를 구해라 해설: m번만큼 L->W를 바꿔서 얻을 수 있는 경우의 수는 3가지다 1) W와 W 사이에 존재하는 L을 변경하였을때 => +3 포인트를 얻을 수 있다. (WLW ->WWW : +2,+1) 2) W의 뒤에 존재하는 L을 변경하였을때 => +2 포인트를 얻을 수 있다. (WLL - >WW..

codeforces.com/contest/1427/problem/A Problem - A - Codeforces codeforces.com 문제 : 배열 a 가 주어지고 a를 재배열해서 b 배열을 만든다. 이때 조건은 처음부터 순차적으로 더했을때 0이 생기면 안되게 만들어야 된다. 해설 : 1) a의 원소들을 전부 더했을때 0이면 "NO" 2) a의 원소들을 전부 더했을때 0이 아니면 "YES" 2-1)이때 다 더했을때 0보다 크면 내림차순으로 정렬해주고 2-2)다 더했을때 0보다 작으면 오름차순으로 정렬해 주면 된다. =>이렇게 해주면 중간에 0이 발생하는 구간이 생기지 않는다. #include using namespace std; using ll = long long; void solve(); boo..

https://www.acmicpc.net/problem/12755 12755번: 수면 장애 수면 장애를 가진 강민이는 잠이 오지 않아 적잖은 고통을 느끼고 있다. 강민이는 잠이 오지 않을 때마다 속으로 양을 세고 있었는데, 오늘따라 백만 마리까지 세었는데도 잠이 오지 않았다. 한 www.acmicpc.net 개인적으로 너무 힘들게 풀었던 문제입니다. 이걸 대체 어떻게 푸나,,,,싶었는데 풀었네요. 1. 입력된 input(=n) 값을 가지고 증가하는 수의 자릿수를 매번 빼준다면 결국에는 1억번의 연산 밑이 될거라는 생각으로 문제를 접근하였습니다. 2. 수를 1씩 증가시켜 주면서 이 수가 몇자리수(ret) 인지 계산을 해줍니다. 3. n 값에서 ret 값을 매번 빼줍니다. 4. n 이 0이 거나 0보다 작..

[문제] : https://www.acmicpc.net/problem/8012 8012번: 한동이는 영업사원! 문제 한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 따라, 한동이는 회사에서 돌아야 할 도시의 목록을 받고, 그 목록대로 도시를 여행한다. 회사에서 주는 여행지 목록은 정말 안타깝게도 최적화되어 있지가 않다. 여행을 떠나기 전에 한동이는 모든 도시를 방문하는데 걸리는 최소의 시간을 알고싶어하는데, 한동이는 경영학과라 컴퓨 www.acmicpc.net [분류] : LCA 알고리즘 [조건]: 가장 핵심적이고 중요한 조건은 "도로끼리 사이클을 만들지 않는다."입니다...

[문제] : https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 www.acmicpc.net [조건] : N개의 섬과 M개의 다리가 주어지며 각 다리에는 물품의 무게를 최대로 버틸수 있는 중량제한 W가 주어집니다.A섬 ..

[문제] : https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 ≤ ai, hi ≤ 1,000,000) 가 주어집니다. ti가 1인 경우 공격력이 ai이고 생명력이 hi인 몬스터가 있음을 나타내고, ti가 2인 경우 용사의 공격력 HATK를 ai만큼 증가시켜주 www.acmicpc.net [분류] :이분탐색(파라메트릭) [조건] : 1)용사의 공격력(atk)이 주어진다. 2)N만큼의 방이 존재하며 a가 1일..

[문제] : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net [분류] : 다이나믹 프로그래밍(DP) [구현 방법] : 유명하고(well known) dp문제를 두고 보면 빠지지 않고 나오는 문제 입니다. 흔히 "냅섹(knapsack)"문제라고 불립니다. 물건 하나씩 더해가면서 현재 가방의 무게가 w 일때 최대로 담을 수 있는 가..