Kyle & I

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 보자마자 거꾸로 가면 된다는 거는 알았는데 치명적인 예외가 있었다. t 가 s 보다 짧은 예외도 들어올 수 있다;;;;; 그 예외를 처리해주니 맞았다! 코드를 보면 심플하니 바로 이해가 될 것이다. #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0)..

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 입출력이 참 힘든 자바로 넘어와서 문제를 풀었다. 처음에 문제보고 어떻게 풀지 고민하다가 답도 없어서 알고리즘 분류를 살짝 봤더니 dp 였다. dp 인 거를 알고 나서 보니까 좀 고민하다가 풀었는데 문제를 보고 어떤 유형인지 알아내는 거를 잘 해야겠다. 풀고나서 보니 매우 유명한 dp 문제인 것 같다. 문제 좀 더 풀어야겠다. dp 문제이니까 우선 점화식을 생각해보자. d[L][R] ..

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 매우 기초적인 DP 문제이다. 하지만 문제는 그게 아니다. 드디어 c++ 에서 자바로 넘어가기 시도 중이다. 자바는 고통이다. 하 무슨 입력 받는거 부터 매우 불편하다. c++ 이었으면 슉샥슉샥 쇽 하고 끝났을텐데 이건 정말 입출력이 짜증난다. 사실 다 그지같다. 하 풀이는 그냥 대각선, 왼, 오 중에서 제일 큰 거 받아와서 현재 값이랑 더해주면 끝이다. import java.io...

https://www.acmicpc.net/problem/23559 23559번: 밥 제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다. 준원이는 대면 수업이 시작되는 바람에 이제 남 www.acmicpc.net programmers 만 풀다가 오랜만에 백준 문제를 풀었다! 문제를 읽어보면 딱 봐도 그리디이다. 처음에는 맛 / 가격 을 해서 효율을 따지려 했는데 문제에서 주어진 첫 예제부터 이게 아니라는 것을 알았다. 예제 입력 1 에서 40 / 5000 < 10 / 1000 인데 첫 날 5000 짜리 메뉴를 고르는 게 정답이다. 다음 생각한 것은 아주 그리디하게 1. 일단 전부 1000원 짜리 메..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 매우 짜증나는 문제였다. 처음 든 생각은 쓸 수 있는 버튼으로 주어진 번호와 가장 가까운 숫자를 찾아내는 게 목표라고 생각했다. 그래서 주어진 번호를 자릿수를 어떻게 하다보면 될 줄 알았는데 결국 안되었다. 그래서 그 다음 생각해낸 방법이 그냥 주어진 번호부터 시작해서 1 씩 더하거나 빼면서 쓸 수 없는 버튼이 포함되어 있으면 넘어가고 누를 수 있는 번호면 멈춘 다음 그 번호를 입..

https://www.acmicpc.net/problem/12107 12107번: 약수 지우기 게임 1 N=4인 경우, A는 처음에 4,2,1을 지운다. 칠판에 남은 수는 3으로, B는 3을 지울 수밖에 없어 패배한다. www.acmicpc.net 아 이런 아이디어 문제 너무 싫다. 이런 거를 어떻게 생각해내는지 모르겠다. 이 문제를 풀 때 가장 중요한 것은 1 은 모든 수의 약수라는 것이다. 풀이를 해보면 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 이 있다 하면 (16이든 뭐든 상관없다). 여기서 1을 잠깐 빼고 생각해보자. 2~16 으로 게임을 할 때 만약 먼저 시작하는 사람이 진다고 가정하면 실제 게임인 1~16 에서는 먼저 시작하는 사람이 처음에 1 을 고르면 2~16이..