전체 글

https://www.acmicpc.net/problem/17268 17268번: 미팅의 저주 인하대 컴퓨터 공학과에 재학 중인 이산이는 오랜만에 미팅을 나가 볼까 한다. 미팅은 N명이 원탁에 앉아서 진행된다고 한다. 질투가 난 이산이 친구 명기는 X의 저주를 걸었다. 그 저주는 N명이 동시에 2명씩 짝을 지어 악수할 때 사람의 팔이 교차되거나 한 사람이라도 악수를 하지 못하면 그 미팅은 실패하게 되는 저주다. 하지만 명기는 이산이에게 저주를 풀 기회를 주었다. 미팅에 성공할 경우의 수를 구하여 큰소리로 외치면 저주가 풀린다. 하지만 이산이는 계산 www.acmicpc.net 짝수의 사람이 둘 씩 짝지어 악수를 할 때, 둘을 이은 선들이 겹치지 않는 경우의 수를 구하는 문제이다. 머리속으로 바로 상상하기..

https://www.acmicpc.net/problem/17267 17267번: 상남자 CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하지 않는다. 하지만 영조의 행동이 답답한 영조의 친구 보성이는 영조가 위, 아래로만 가는 걸 막기 위해 영조와 같이 다니며 왼쪽으로 최대 L번 오른쪽으로 최대 R번만큼 이동할 수 있게 영조를 도와준다. 영조와 보성이는 지도 밖으로는 나가지 않는다. 갈수 있는 땅, 벽의 www.acmicpc.net 처음 봤을 때, BFS문제인 것은 쉽게 유추할 수 있었지만, 쉽게 틀릴 수 있는 문제였다. 일반적인 BFS처럼 상하좌우 한칸씩 탐색해가며..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 깊게 생각해서 오히려 더 헤맸던 문제였다. 브루트포스로 접근하니 금방 풀린 문제이다. 처음 시작하는 채널은 100번. 리모컨의 부서진 버튼은 배열에 따로 체크해둔다. 그리고, 이 문제에서 가능한 모든 채널을 0번부터 탐색해준다. 약 100만 채널까지 탐색하면 되겠다. 그 채널을 가기 위해 필요한 버튼을 누르는 횟수(0번은 불..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다. 사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시('-'), 마침표('.')로 이루어져 있고, 중복되지 않는다. 비밀번호는 알파벳 대문자로만 이루어져 있다. 모두 길이는 최대 20자이다. N+2번째 줄부터 www.acmicpc.net 사이트 주소와 비밀번호를 페어로 묶은 벡터를 정렬하여, 이분탐색으로 사이트 주소의 위치번호를 찾아내면 쉽게 풀 수 있는 문제이다...