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

www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 문제 : 두 로봇이 있고 같은 통로에 존재하도록 할때 소요되는 거리의 최소값을 구해라 해설 : n개의 정점이 주어지고 n-1개의 간선이 주어질때 무조건 '트리'라는 것을 파악할 수 있어야 된다. 어쨌건 두 로봇은 무조건 같은 통로에 있어야 하니 둘 사이에는 간선이 1개만 존재해야한다. 이는 x->y까지 가는 경로중에 가장 가중치가 높은 간선 1개만 빼주면 된다는 뜻. 정점을 하나씩 탐색해주고 목표(y)..

www.acmicpc.net/problem/16569 16569번: 화산쇄설류 첫 번째 줄에 정수 M, N, V이 공백으로 구분되어 주어진다. (1 ≤ M, N ≤ 100, 1 ≤ V ≤ min(5,000, M×N)) 그 다음 줄에 X, Y가 공백으로 구분되어 주어진다. (1 ≤ X ≤ M, 1 ≤ Y ≤ N) 그 다음 줄부터 M개의 www.acmicpc.net 문제 : 지정된 시간에 화산이 터지고 이 화산은 인접한 칸에 점점 퍼진다. 이때 윤재상이 갈 수 있는 곳 중 가장 높은 고지대의 높이와 도달하기까지 시간을 구해라 해설 : "t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다." 이 말은 화산쇄설류가 인접한 칸으로 1초마다 점점..

www.acmicpc.net/problem/15922 15922번: 아우으 우아으이야!! N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!! www.acmicpc.net 문제 : 수직선이 주어지고 [시작점,끝점] 이 주어진다. 선분은 겹칠 수 있고, 이때 그려지는 선분의 총 길이를 구해라 해설 : 간단히 생각해서 선분이 겹칠 경우만 잘 걸러주면 된다. 문제에서 x 값이 증가되는 순서대로 주어진다고 했으니 선분이 서로 겹치는 경우는 단 하나 밖에 없다. 후에 들어오는 x 좌표가 기존에 존재하는 좌표의 y 값보다 작거나 같을때 [x1] ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ [y1] [x2] ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ[..

www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직 www.acmicpc.net 문제 : 'E' 와 'W'가 주어지고 선물을 구사과님이 어느 칸에서부터 시작하더라도 먹을 수 있도록 배치해야된다. 이때 최소의 선물만 배치해야된다. 해설 : 'E'로 시작하면 'W'를 만나지 않을때까지 전진한다. 그리고 'W'를 만나면 다시 돌아간다. 이는 'E'의 끝에 선물을 하나 놓으면 이 위치를 기준으로 왼쪽으로는 'E' 오른쪽으로는 'W'는 무조건 선물을 먹게 된다는 뜻. ex) EEEEEE..

www.acmicpc.net/problem/11565 11565번: 바이너리 게임 첫 번째 줄에는 문자열 a, 두 번째 줄에는 문자열 b가 주어진다. 두 문자열은 0과 1로만 이루어져 있으며, 문자열 a와 문자열 b의 길이는 1 이상 1,000 이하이다. www.acmicpc.net 문제 : 문자열 a,b가 주어지고 a를 b로 만들 수 있는가?를 묻고 있음. 규칙 1 : 맨 앞문자를 지울 수 있음 규칙 2 : 맨 뒤에 문자를 추가할 수 있음. 이때 1이 홀수개이면 1을 나머지는 0을 추가 해설 : 와,,,이런문제 너무 싫어요....근데 또 재밌어 ㅋㅋㅋ(전형적으로 codeforces 에서 나올 법한 문제) 문제에 말리면 절대 풀 수 없는 문제. 결론부터 말하면 a와 b가 어떻게 생겨먹었든 전혀 상관 없다..

www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문제 : 문자열뒤에 'A'를 추가하거나, 뒤집고 'B'를 추가하거나 해서 주어진 문자열을 만들어라 해설 : 거꾸로 생각해 보자. S를 T로 만든다고 생각하는게 아닌 T를 S로 만든다고 생각하자. 왜 이렇게 생각을 해보는 걸까? 결국 결과물은 T이기 때문이다. T를 S로 만들기 위해 'A' 나 'B'를 제거하면서 S가 나온다면 만들 수 있는 것이고, 만약 T의 문자열이 0이 ..

www.acmicpc.net/problem/13273 13273번: 로마숫자 각 테스트 케이스에 대해서 로마 숫자가 주어지면 그 숫자에 해당하는 아라비아 숫자를 출력하고, 아라비아 숫자가 주어지면 그 숫자에 해당하는 로마 숫자를 출력하여라. www.acmicpc.net 문제 : 수가 주어지면 문자열로,문자열이 주어지면 수로 변환해서 출력해라 해설 : 천천히 조목조목 구현하면 된다. #include using namespace std; void solve(); string INT(string s); int STR(string s); int main() { int t; cin >> t; while (t--) solve(); } void solve() { string s; cin >> s; if ('0'

www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 문제 : 트리의 개수를 구해라. (이때, x==y 인 조건은 배제해도 된다. 적어도 이 문제에는 x==y인 데이터는 존재하지 않음) 해설 : 뭐 각자 선호하는 방식으로 풀면 된다. disjoint-set 개념을 이용해도 되고 dfs를 이용해서 구해도 되고. 저는 dfs로 구했습니다. 이때 트리라는 것을 체크하는 방법이 여러가지 존재한다고 하네요. 전 끝까지 갔을때 싸이클이 존재하면 false를..

www.acmicpc.net/problem/1833 1833번: 고속철도 설계하기 첫째 줄에 두 정수 C, M를 출력한다. C는 고속철도망을 설치하는데 든 총 비용이며, M은 새로이 설치한 고속철도의 개수이다. 다음 M개의 줄에는 새로 고속철도가 설치된 두 도시번호를 출력한다. www.acmicpc.net 문제 : 이미 설치되어 있는 철도가 있고 새로 지어야 되는 철도가 주어진다. 이때 (이미 지어진 철도의 가중치) + (새로 지어야 되는 철도의 가중치)의 최소값을 구해라 해설 : 입력값이 음수로 들어오면 이미 연결되어있으니깐 정답에 더해주고 부모들을 합쳐준다. 나머지는 그냥 평범한 mst 문제 #include using namespace std; struct info { int x, y, w; bool..

www.acmicpc.net/problem/12739 12739번: 돌림판 (Small) 지훈이는 경품 이벤트를 진행하기 위해서 원형판이 N등분 되어 있고, 각 N등분된 곳에 빨간색 또는 초록색 또는 파란색이 색칠되어 있는 돌림판을 준비하였다. 이 이벤트의 룰은 간단하다. 이벤 www.acmicpc.net 문제 : 조건에 맞게 하나씩 시뮬레이션 돌리면 된다. 해설 : 주의할점은 '동시에' 돌림판들이 바뀌어야 된다는 점. 이를 위해 새로운 문자열을 선언한 후 이를 붙여넣고 다시 비교해주는 식으로 구현해 주자. 실수만 없다면 다들 잘 풀 수 있는 문제!! #include using namespace std; int n, k; int arr[1000]; string s; int draw(int x); int ..

www.acmicpc.net/problem/7682 7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net 문제 : 틱택토가 될 수 있는 경우의 수가 주어졌을때만 valid 아니면 invalid 를 출력해라. 해설 : 처음에 예시랑 문제보고 뭔 멍멍이소리인가 싶었음. 알고보니 한줄씩 9문자를 차례대로 3x3 보드에 넣는 거였음 안될 조건을 찾는게 은근 까다로움,,,, 하나씩 살펴보자 끝낼 조건 : 가로/세로/대각선 중 하나라도 3개가 연다라 붙어있으면 끝, 아닐때 보드의 칸은 X,O로 가득 채워져야함 ..

www.acmicpc.net/problem/2758 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 문제 : n,m이 주어지고 선영이는 전에 골랐던 수카드의 2배 이상의 카드를 n 개 고를 수 있다. 수는 m까지 적혀있는 카드이다. 해설 : 2차원 테이블로 작은 범위의 수들을 저장해 주면서 하나씩 뽑아내 오자. 뭔 개떡같은 그림이냐고 할 수 있겠지만, ㅈㅅ하다,,,,,그림판으로 그린거라 ㅠㅠ 설명을 하자면 dp[n][m] = n번째에 m이하의 수가 올수 있는 경우의 수 이다. ex)dp[4][10] = 4번째에 10부..