https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 개인적으로 아이디어를 떠올리기가 조금 까다로운 문제였습니다. dp를 어떻게 효율적으로 할 지 까다로웠지만 제가 사용한 방법은 다음과 같습니다. dp[ i ][ j ][ k ] = i번째에 j라는 수가 들어갔고 이 때 k만큼 체크된 상황 이라고 할 때 (1번째는 왼쪽을 기준입니다.) (체크는 비트스트링을 이용합니다.) dp[ i ][ j ][ k | (1
https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net map 자료구조를 이용해 풀었습니다. 피자를 n^2으로 start 번호부터 piece개 (정확히는 piece + 1개)를 돌면서 합을 구해줍니다. 그리고 map에 해당 합의 값을 찾아 +1 을 해줍니다. 최종적으로 맵 중 하나를 골라 iterator를 돌리면서 나머지 피자의 양을 다른 맵에서 찾아줍니다. 벡터에 넣고 바이너리 서치를 해도 될 거 같지만 map을 이용해도 풀릴 것..
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 주어진 수열의 오른쪽에 있는 수 중 수열에 나온 횟수가 더 큰 가장 왼쪽의 수를 구하는 문제입니다. 예를 들어, 1,2,1,1,3,3,1 로 주어졌다면, 가장 오른쪽의 1보다 더 오른쪽의 수는 없으므로 -1, 그 다음 3은 2번 나왔지만, 오른쪽의 1은 4번 나왔으므로 1, 2의 경우 오른쪽의 1은 4번, 3은 2번 나왔지만, 2를 기준으로 1이 더 왼쪽에 있으므로 1이 정답입니다. 스택 2개를 이용해 스택에..
https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 누적합문제였습니다. 처음 입력 받을 때부터 앞에 해당 알파벳이 몇 개 있는 지 확인 후, 해당 위치에 그 알파벳이 있으면 +1, 아니면 그냥 가져갑니다. 그리고 쿼리 시, l번째에 해당 알파벳이 있다면 dp[r] - dp[l] + 1, 없다면 dp[r] - dp[l] 을 하면 됩니다. (몇 가지 케이스를 그려보면 쉽게 구할 수 있습니다.) 코드는 ..
https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 보드에 적힌 수만큼 상하좌우로 이동할 수 있을 때 보드를 벗어나거나 구멍에 빠질 때까지 움직일 수 있는 횟수를 구하는 문제입니다. 루프가 발생하면 -1을 출력합니다. 처음에 dfs만으로 풀려다 계속 시간초과가 나서 dp를 추가하여 풀었습니다. dfs로 돌면서 밖에 가거나 구멍인 경우, 해당 위치에서 더 이상 움직일 수 없으므로 0을 리턴하고, 이동 가능한 경우, 상하좌우로 움직이면서 dfs를 돈 ..