https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 생각하기 너무 힘들었다.. 그래서 다른 사람의 해결책을 보면서 원리를 이해했다. 이 문제에서의 핵심은 메모리를 관리하는 것이다. 그래서 동전의 사용을 dp로 저장하였다. 동작 방식은 먼저 0부터 k까지의 수를 만드는 과정을 기록할 배열을 둔다고 생각한다. 예를 들어 n=3 k=10이고 1,2,5가 동전으로 주어졌다고 생각해보자.(설명에서 헷갈리는 것을 줄이기 위해 동전을 one,two,..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 오늘 푼 문제는 누적합과 투 포인터를 이용하는 문제였다. 나는 이 문제의 접근방식은 맞았지만 구현하는 과정에서 조건문을 처리하는 것에서 문제가 있어서 애를 먹었다.. 또 감자 짓도 해서 문제를 잘못 읽어 S인 값을 찾는다고 생각해버렸다.. 하지만 문제에는 S이상인 값이었다... 어쨌든 그래서 이 문제의 풀이 방법을 설명해보면 슬라이딩 윈도우 알고리즘이라고 생각하면 된다. 물론 슬라이..
https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 이 문제는 25682번과 완전 같은 코드이다. 먼저 N,M을 입력 받고, chess판을 채우기위한 값들을 입력받고, 그 다음에 시작지점이 검은색일때와 흰색일 때로 나누어서 생각한다. 그렇게 시작점과 같은색인 부분, 시작지점과 다른색인 부분을 (i+j)%2==0의 조건으로 판별해서 누적합을 계산한다. 물론 이 문제에서는 브루트포스법을 사용하라는 의도로 내었다. 브루트 포스로 한다면, 위의 조..
https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 이 문제는 생각해내는 것 조차 어려웠다. 일단 체스판의 테이블을 만들고 누적합을 구해야한다는 생각은 했지만, 어떤 것의 누적합을 구해야 할지 몰랐다. 그래서 처음에는 테이블 자체의 누적합을 이용해서 해야하는건지 고민하느라 오래걸렸고, 그러다가 다른 사람들이 질문게시판에 올린 글을 보고, 틀린것을 누적합으로 계산하는 것이 맞겠다는걸 알았다. 그래서 이 문제를 틀린 것에 대한 누적합을 구하는 방법으로 생각했다. 풀이에서 경우의 수는 2가지이..
https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 처음 이 문제를 봤을 때는 그냥 주어진 문자열과 주어진 시작,끝 인덱스를 이용해서 비교값과 같으면 count값을 증가시키는 방식을 생각해냈다. 하지만 그렇게 했더니 50점만 받을 수 있었다. 이 문제에서 바라는 것은 누적합계산이었다. 즉, 값 저장 배열을 만들어서 누적된 계산의 합을 구하라는 것이다. 그래서 표를 만들었다. joon이라는 문자열이 ..
