https://www.acmicpc.net/problem/28458 28458번: Mahjong Tenpai 3통을 가져왔을 경우 3삭 2개를 머리로 사용한 후 3삭 4삭 5삭의 슌쯔를 몸통1, 3삭 4삭 5삭의 슌쯔를 몸통3, 1통 2통 3통의 슌쯔를 몸통3, 3통 3통 3통의 커쯔를 몸통4로 볼 수 있다. 6삭을 가져왔을 경 www.acmicpc.net 주어진 마작패가 대기패인지 아닌지 판별하고 대기패라면 완성패가 되기 위해 추가해야 하는 패를 출력하는 문제이다. 일단 대기패의 구성 숫자가 13장이고, 완성패의 구성숫자가 14장으로 크지 않고 패의 종류도 많지 않아서 브루트포스를 돌리면 되겠다고 생각했다. 그래서 34종류의 모든 패를 하나씩 대기패에 추가해보고 그렇게 구성한 패가 완성패인지 아닌지 판..
https://www.acmicpc.net/problem/28457 28457번: Every? Only One's Marble 첫 번째 줄에는 보드의 크기 $n$, 시작 시 가지는 돈 $S$, 시작점을 지나면 받게 되는 월급 $W$, 황금 열쇠 카드의 개수 $G$가 주어진다. ($3\leq n\leq 10$, $1\leq G\leq 4n-8$, $1\leq S,W\leq 10^7$) 그다음 $G$개의 www.acmicpc.net 부루마블 게임을 구현하는 문제다. 그래도 플레이어가 1명이라 구현 난이도가 엄청 높진 않다. (플레이어가 여러명인 Yut Nori 같은 문제 구현에 비하면..) 구현할 때 다음과 같은 2가지 사항에 주의해야했다. 1. 보드의 사이즈가 작을 때는 주사위 한번으로 2바퀴를 돌 수도 ..
https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 개인적으로 플레 난이도 치고는 풀만한 문제라고 생각한다. 중복되는 키가 연속으로 들어오는 경우를 체크하는게 고민 포인트. 내가 푼 알고리즘은 다음과 같다. 0. 맨 처음에 들어오는 키는 그냥 스택에 넣는다. 1. 수를 입력받으면 해당 수와 스택의 탑에 있는 값을 비교한다. 1.1 탑에 있는 값 > 새로 들어온 값 인 경우 (키가 감소) 탑에 있는 값과 새로 들어온 값이 서로..
https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 난이도가 조금 있는 스택문제 알고리즘 분류가 스택이라는 것만 알아내면 아이디어가 어렵다기 보다는 구현이 조금 복잡하다고 생각한다. 오등큰수를 결정하는 제일 큰 기준은 '숫자의 등장 횟수' 이다. 따라서 숫자의 등장횟수를 미리 다 저장해둔다. 주어진 수열의 왼쪽부터 차례대로 순회하면서 해당 숫자의 등장 횟수를 스택에 저장해나가다 스택의 가장 위에 있는 수의 등장횟수보다 더 많은 등장횟수를 가진 수가 나타나면 그..
https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 모든 가로수의 간격이 같도록 새로 심어야 하는 가로수의 최소 개수를 구하는 문제이다. (최대 개수로 심으려면 그냥 간격을 1씩 해서 심으면 되니 간단하다) 바꿔말하면 주어진 수열이 등차수열이 되도록 하는 공차의 최댓값을 구하는 문제로 볼 수 있다. 등차수열의 일반항 An = a + (n-1)d 으로 생각을 해보면 구하는게 공차의 최댓값이니 공차를 구하는데 방해가 되는 초항 a 를 없애준다...
https://www.acmicpc.net/problem/1796 1796번: 신기한 키보드 동혁이의 키보드에는 버튼 세 개와 LCD창 한 개가 달려 있다. LCD창에는 문자열 S가 쓰여 있다. 그리고 커서는 문자열의 가장 왼쪽 글자에 위치해 있다. 버튼 세 개는 왼쪽, 오른쪽, 엔터키이다. 왼 www.acmicpc.net 옛날에 봤을 땐 분명 골드5 문제였는데 어느샌가 골드4로 올라간 문제이다. 풀고나서 보니까 왜 누구는 골드5로, 누구는 실버1로 매겼는지 알 것 같았다. 문제 상황을 프로그래밍적으로? 정의하고 나면 되게 간단해지기 때문이다. 그런데 이 문제는 그 정의가 어려운 문제였다 그래서 나도 이 문제 난이도에 골드4를 줬다. 문제는 간단하다. 좌우버튼과 엔터 버튼만으로 구성된 키보드를 이용해 주..
전에 풀었던 문제인데 2달전 재채점 때 틀려서 다시 풀어보았다. 다시 풀려니까 도저히 풀리질 않아서 외판원 순회 아이디어를 읽었는데도 모르겠었다. 그래서 결국 내가 전에 티스토리에 썼던 글을 보았는데, 신기하게 그걸 보니까 작성할 수 있었다. 나는 내가 제일 잘 아는건가ㅋㅋ 하지만 그 글에서 헷갈렸던 부분이 있어서 다시 정리하려고 한다. 1. 외판원 순회는 어디에서 시작해도 값이 같다. "도시" 가 아니라 "간선" 을 기준으로 보면 바로 이해된다. 1-3-2-1 이 최적해라고 하자. 그럼 최적해를 구성하는 간선은 1-3 3-2 2-1 이렇게 3개이다. 만약 3에서 시작했다고 하면 최적해는 3-2-1-3 이렇게 된다. 최적해의 구성 간선은 3-2 2-1 1-3 순서만 다르지 아까와 똑같다. 따라서 어디에서..
https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 처음엔 그림만 보고 그래프 문제를 예상했는데, 문제를 읽어보니 경우의 수를 세라길래 DP로 예상해서 DP 점화식을 세웠다. 근데 dp테이블을 일일히 채우고 있다가는 저 10억이라는 입력데이터를 감당하지 못하겠다는 생각이 들었다. 그래서 결국 알고리즘 분류를 봤다.. 그런데 띠용.. '분할정복을 이용한 거듭제곱' 문제라고 소개가 되어있었다. 다행히 이걸 보고 전에 풀었던 피보나치 문제가 스쳐지나갔다. 행렬 거듭제곱을 이용해서 피보나치 수열을 빠르게 구하는 문제였다. 그런데 부끄럽게도 그 문제를 풀 당시에는 피보나치..
https://www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 자료구조를 이용한 깡 구현 문제이다. 구현문제아니랄까 한글자 오타난 걸 디버깅하느라 애를 먹었다. (무수한 assert 문 제출 시도..) 맨 앞의 연산자 / 맨 뒤의 연산자 둘중 하나를 골라서 스택처럼 처리해야하므로 덱을 이용했다. 파이썬으로 풀 때 음수 나눗셈에 주의하고, 음수 하나만 입력으로 들어오는 코너케이스를 주의하면 어렵지 않게 풀 수 있다. from ..
https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 이분 탐색을 쓰면 좋겠다고 떠올렸지만, 한번 쓴 카드를 다시 쓰지 않도록 체크하는 부분을 어떻게 해야할지 떠올리지 못했던 문제이다. 결국 알고리즘 분류를 통해 힌트를 얻고 풀었다. 분리집합을 보고 처음에는 어떻게 분리집합을 이용해서 풀 수 있을지 감이 안잡혔는데, 노트에 생각을 정리하다보니 아이디어가 떠올랐다. 이분탐색, 특히 upper bou..
