🔗문제 보러가기 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 🧑‍💻풀이 과정 네트워크에서 TCP 프로토콜을 공부할 때 봤었던 슬라이딩 윈도우(Sliding window) 개념을 적용하여 풀 수 있습니다. 입력으로 주어지는 각 숫자들을 배열(arr)에 저장하되, [0, K - 1]까지의 합계를 별도의 변수(sum)에 저장해둡니다. int start = 0, last = K로 인덱스 변수를 둡니다. 정답 변수(maxSum)을 1번에서 구한 sum 변수 값으로 초기화합니다. last < K가 만족할..

🔗문제 보러가기 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 🧑‍💻풀이 과정 나의 멍청한 실수 이전 문제에서 누적 합을 잘 구해놓고, 여기에서는 왜 적용을 못했나 싶습니다.. 처음에는 DP[26][S.length()] 배열을 선언하여, 각 알파벳마다 등장한 횟수를 누적하여 저장하는 방식으로 접근하였습니다. const int ALPHABET_COUNT = 26; const int LOWER_A_ASCII = 97; string S; vector DP(ALPHA..

🔗문제 보러가기 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 🧑‍💻풀이 과정 백준 사이트에서 단계별 풀어보기를 차례대로 정복 중인데, 그 중 누적 합이라는 유형에 대한 첫 문제였습니다. 문제를 보자마자 딱 생각난 것은, 통계학에서 쓰이는 누적분포함수(CDF, Cumulative Distribution Function)였습니다. 물론 개념적으로 완전히 동일한 것은 아니지만, 제 풀이의 기반 아이디어가 되어 주었습니다. 해당 아이디어를 토대로, 다음과 같이 문제를 순차적으로 풀 수 있습니..

🔗문제 보러가기 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🧑🏻‍💻풀이 과정 N자리 숫자에서 일의 자리가 0 ~ 9로 끝나는 계단 수들의 개수를 알아봅시다. 먼저, \( N = 1\)일 때는 다음과 같습니다. [ N = 1 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 0 1 1 1 1 1 1 1 1 1 [ N = 2 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 1 1 2 2 2 2 2 2 2 1 [ N = 3 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i..

🔗문제 보러가기 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 🧑🏻‍💻풀이 과정 문제 로직 자체는 어렵지 않은데, 구현할 게 많아서 상당히 귀찮았던 문제입니다. 문제를 보면, 다음과 같은 문장을 읽을 수 있습니다. 뱀의 머리가 먼저 한 칸 이동합니다. 그 위치에 사과가 없다면, 꼬리도 한 칸 이동하고, 사과가 있다면 꼬리는 이동하지 않습니다. 위 문장을 구현하려면, 뱀의 꼬리가 이동할 방향에 대한 정보가 필요합니다. 뱀의 꼬리가 이동해야 할 방향은 이전까지 뱀의 머리가 이동했던 방향들이므로, 뱀의 머리가 이동했던 ..

🔗문제 보러가기 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 🧑🏻‍💻풀이 과정 에너지 값들을 vector weights에 저장한 후, weights의 크기가 2가 될 때까지 다음 과정을 반복합니다. 정답을 저장할 변수(maxEnegy)와 현재 경우의 수의 합계를 저장할 변수(sum)를 생성합니다. weights를 i = 1부터 i = weights.size() - 1까지 for 문으로 순회합니다. weights[i - 1] x weights[i + 1]의 값을 sum에 더합니다. weights[i] 원..