🔗문제 보러가기 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 🧑🏻‍💻풀이 과정 각각 N행 M열 크기의 흰색으로 시작하는 보드판과 검은색으로 시작하는 보드판 두 개의 2차원 배열을 준비합니다. 다음 과정을 통해, 교체해야 하는 횟수를 누적하여 저장해 나갑니다. 다음은 올바른 체스판의 배열일 경우를 나타냅니다. (행 + 열)이 짝수일 경우, 시작 색깔(1, 1)과 같아야 한다. (행 + 열)이 홀수일 경우, 시작 색깔(1, 1)과 달라야 한다. 위 두 가지 중 하나에 해당하지 않을 경우, 색깔을 교체해야 한다. 행과 열을 각각 K부터 시작하여, 각각 ..

🔗문제 보러가기 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 🧑‍💻풀이 과정 초기값으로, 1행과 1열 각각의 배열 원소에 누적합을 저장합니다. 2행 2열 ~ N행 N열까지 다음 과정을 반복합니다. \( N \times N \) 배열을 arr이라고 한다면, arr[row][col] += arr[row - 1][col] + arr[row][col - 1] - arr[row - 1][col - 1] arr[row - 1][col]에는 (row - 1 ) * col 사각형..

🔗문제 보러가기 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..