왕도를 찾아서

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 플래티넘 입문하기 좋은 문제다. 비슷한 느낌의 문제로 탑이 있다. https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.n..

https://www.acmicpc.net/problem/3358 3358번: Towers of coins Asen and Boyan are playing the following game. They choose two different positive integers K and L, and start the game with a tower of N coins. Asen always plays first, Boyan – second, after that – Asen again, then Boyan, and so on. The boy in turn can www.acmicpc.net 게임이론 문제이면서 DP로 푸는 문제다... 사실상 돌 게임 6이랑 똑같은 문제다. https://www.acmicpc.ne..

https://www.acmicpc.net/problem/16888 16888번: 루트 게임 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 105)가 주어진다. 둘째 줄부터 T개의 줄에 테스트 케이스가 한 줄에 하나씩 주어지며, N(1 ≤ N ≤ 106)이 주어진다. www.acmicpc.net 게임 이론 문제는 DP로 풀어야 하는 게 있고 규칙성을 찾아야 하는 게 있는데 이건 DP로 푸는 문제다. STEP 0. bool dp[] 배열을 생각해보자 dp[i]에는 내 차례에 숫자가 i일때 내가 이기면 true, 내가 지면 false값을 저장한다. 그럼 일단 dp[1]=1, dp[4]=1, dp[9]=1, ...... 모든 제곱수 i에 대해 dp[i]=1이다. STEP 1. i가 제곱수가 아니라면 i 이..

https://www.acmicpc.net/problem/24678 24678번: 돌무더기 게임 1 첫 번째 케이스에서 R의 첫 시행 이후 가능한 다음 상태는 $(0,0,2), (0,2,0), (2,0,0)$뿐이며, B는 더 이상 시행을 할 수 없으므로 이긴다. 두 번째 케이스에서 R의 첫 시행 이후 가능한 다음 상태는 다음 www.acmicpc.net 풀이를 한 100줄 쓴 거 같은데... 쓰다가 다 지워버렸다. 너무 간단한 풀이가 생각나서 돌무더기가 내 차례에 짝수 짝수 짝수 상태로 놓여있다고 생각해보자 그럼 상대편 차례일때는 무조건 홀수 홀수 홀수 일 것이다. 왜냐하면 각 돌무더기에 대해 돌 하나를 가져가거나 올려놓거나 하니까 짝수는 홀수로 홀수는 짝수로 바꾸는 거다. 그리고 내 차례엔 무조건 짝수..

https://www.acmicpc.net/problem/26156 26156번: 나락도 락이다 NAROCK, NAROCK, NAROCK, NAROCK 총 4개이다. www.acmicpc.net 나락도 락이다. 부모님께 온 연락도 락이다. 오락가락?도 락? 이다.? 일단은 입력받은 문자열의 부분열 중 ROCK의 개수가 몇개 있는지 찾아줘야 한다는 문제이다. STEP 0. 문자열 S의 부분열 중 "K"이 몇개 있는지 찾는다. 이를 이용해 S의 부분열 중 "CK"이 몇 개 있는지 찾을 수 있고, 이를 이용해 S의 부분열 중 "OCK"이 몇 개 있는지 찾을 수 있고, 이를 이용해 S의 부분열 중 "ROCK"이 몇 개 있는지 찾을 수 있다. S를 i번째 이후 문자부터만 셌을 때 부분열 중 문자열 "K"가 몇 개..

https://www.acmicpc.net/problem/11390 11390번: 맛있는 과자 첫 번째 줄에 네 개의 자연수 a, b, N, K (1 ≤ a, b ≤ 100, 1 ≤ N ≤ 40, 1 ≤ K ≤ 2N)이 공백을 사이로 두고 주어진다. www.acmicpc.net DP문제를 돌다가 발견했는데 알고보니 그냥 수학문제. DP인 이유는 조합을 이용하기 때문이다. STEP 0. DP를 이용해 nCk (조합, Combination) 값들을 전부 배열 co[n][k]에 저장해준다. STEP 1. 두 삼각형의 넓이비는 a^2 : b^2. 왜 그런지는 중학교 때 배운다. a와 b를 입력받는데, a가 b보다 더 큰 값이라고 가정해보자. 어차피 입력받은 뒤 작은 게 a가 되도록 수정하면 되니 상관 X. A=..

https://www.acmicpc.net/problem/19847 19847번: 여우 신탁 “여우신님, 여우신님, 번호 하나만 내려 주세요…” 누구나 1 이상 45 이하의 정수 여섯 개를 잘 골라서 인생이 달라지거나, 혹은 1 이상 10,000 이하의 정수 하나를 잘 골라서 맞았습니다!!를 받는 www.acmicpc.net 예를 들어 일단 첫 여우는 9개의 수 중 하나를 달라고 할 것이다. 그러면 9개의 숫자들이 나올 확률은 전부 같다. 즉, 각 숫자가 뽑히는 경우의 수를 저장한 배열은 int p[]={1,1,1,1,1,1,1,1,1}; 로 나타낼 수 있다. STEP 0. 입력 두 번째 줄에 받는 숫자들이 예를 들어 9 4 2 라면 여우신은 4 이상 수들은 전부 4로 나눈 나머지를 계산해야 하고, 또 ..

https://www.acmicpc.net/problem/1955 1955번: 수식 표현 수식 표현이란 1, +, *, !, (, )로만 이루어진 수식을 말한다. 간명하게 정의하기 위해, 다음과 같이 귀납적으로 정의할 수 있다. 1은 수식표현이다. e가 수식표현이면 (e)와 e!도 수식표현이다. e1과 e2 www.acmicpc.net 시간복잡도: n이 10000 이하이기 때문에 O(n^2) 안에 풀 수 있어야 한다. PART 0. 입력이 i일때 출력해야할 값을 dp[i]라고 두면 일단 dp[0]~dp[8] 값을 생각해보자면 dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; dp[4] = 4; dp[5] = 5; dp[6] = 3; dp[7] = 4; dp[8] = 5; PA..