문제 이해 단계 https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 정점과 간선 정보가 주어진다. 각 간선은 단방향으로 주어지고, 간선에는 시간이라는 가중치가 존재한다. 여기서 선택해야 하는 것은 왕복 시간(목적지로 갔다가 다시 돌아오는데 드는 시간)이 가장 많이 드는 사람의 시간을 최소화하는 도시를 선택하는 것이다. 도시의 개수 N과 간선의 개수 M, 그리고 사람 수 K와 각 사람이 사는 도시 정보가 주어진다. 왕복 시간이 가장 많이 드는 사람의 시간을 최소화하는 도시를 출력하고, 만약 여러 개..

문제 이해 단계 https://www.acmicpc.net/problem/13019 13019번: A를 B로 첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다. www.acmicpc.net 대문자 알파벳으로 이루어진 문자열 A와 B가 입력으로 들어온다. 문자열 A를 B로 바꾸는 것이 목표. 할 수 있는 연산은 알파벳 하나를 골라 가장 앞으로 보내는 것이다. 이때 최소 몇 번 만에 만들 수 있는지 구하는 문제 문제 접근 단계 일단 입력으로 들어오는 문자열의 길이가 50이 넘지 않는다. 따라서 시간초과는 크게 신경 쓰지 않아도 될 것 같다. 연산에서 중간에 있는 문자를 골라도 상관이 없다. 하지만 무조건 가장 앞으로 보내..

문제 이해 단계 https://www.acmicpc.net/problem/22945 22945번: 팀 빌딩 능력치가 다 다른 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같 www.acmicpc.net 능력치가 다 다른 N명이 입력으로 들어온다. 이 중에서 2명을 뽑아서 값을 만들 때, 값을 구하는 공식은 아래와 같다. (A와 B 사이에 존재하는 다른 사람 수)*min(A, B) 이러한 조건일 때 나올 수 있는 값의 최대치를 구하는 문제 문제 접근 단계 문제풀이를 위해 조건부터 살펴보자. 들어올 수 있는 사람 N은 최대 100,000까지 가능하고, 능력치는 10,000까지 ..

문제 이해 단계 https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1 N; vector v(N); // 일을 담을 벡터 int avail = 0; for(int i = 0; i > v1 >> v2; v[i] = {v1,v2}; avail = max(avail,v2-v1); // 필요하는 최소 시간이 가장 많은 걸 시작 시간으로 둚 } sort(v.begin(),v.end(),compare); // 정렬 // 0 이상일때까진 반복 while(avail >= 0){ int cnt = avail; // cnt -> 현재 시간 ..

문제 이해 단계 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net A가 B에 의존하면, B가 감염됐을 때 A도 감염된다. 이를 의존이라고 한다. 입력으로 테스트 케이스 T, 컴퓨터 개수 n, 의존성 관계 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다. 의존성 관계 정보는 (a, b, s)로 주어지는데 이는 컴퓨터 a가 컴퓨터 b를 의존하고, b가 감염된 후 s초 후 컴퓨터 a도 감염된다는 뜻이다. 해당 조건일 때 출력으로 컴퓨터 수, 마지막 컴퓨터..

문제 이해 단계 https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 입력으로 가지고 있는 휴게소 N과 만들어야 할 휴게소 M, 고속도로 길이 L이 주어진다. 휴게소를 M개를 더 지어 휴게소 사이의 거리를 최소화하려고 한다. 고속도로 끝과 중복된 곳에 배치하는 것은 금지한다. 휴게소들 사이의 거리가 최소가 되도록 이상적으로 배치했을 때, 그중 구간의 길이가 가장 긴 것을 출력하는 문제 문제 접근 단계 문제가 말을 어렵게 써놔서 이해하는 게 한참 걸렸다. 이 문제의 제한 범..

문제 이해 단계 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 입력으로 직원수 n과 칭찬의 횟수 m이 주어진다. 그리고 직원은 1번부터 n번까지 번호가 매겨져 있다. 해당 문제에서 칭찬은 상사가 직속 부하를 칭찬하면 그 부하가 부하를, 또 그 부하를 연쇄적으로 칭찬하는 내리 칭찬 형식이다. 칭찬에는 각각의 수치가 존재한다. 두 번째 입력으로는 n개의 직속 상사와 부하관계가 주어진다. 직속 상사의 번호는 항상 자신의 번호보다 작다. 그리고 3..

문제 이해 단계 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 입력으로 S가 주어지고, S개의 이모티콘을 만드는 게 목표이다. 다음의 3가지 연산만을 사용하여 S개의 이모티콘을 만들어야 한다. 기본적으로 이모티콘 1개는 입력되어 있다. 문제 조건은 아래와 같다. 1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여 넣기 한다. 3. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산..