코학다식

문제 링크 :: https://www.acmicpc.net/problem/11660 Solution 구간 합을 이용하긴 하는데 이차원 배열임을 유의해야 한다. 문제의 예시에서 볼 수 있듯이 그냥 처음부터 끝까지 수를 다 더하는 게 아니라 사각형 모양을 이루는 구간의 합을 구해야 한다. 이건 구간 합을 구할 때뿐만이 아니라, 부분 합을 구할 때도 마찬가지다. 특정 위치의 부분 합을 구하고 싶다면 처음(1, 1)부터 해당 위치까지 사각형을 만들어 그 구역에 있는 숫자들을 합해야 한다. 합하는 방법은 일차원 배열보다는 조금 복잡하지만 어렵지는 않다. 첫 행은 평범하게 부분 합 구하듯이 쭉쭉 더해 주면 된다. 다음 행부터는 첫 번째 열에 위치하는 경우와 아닌 경우가 달라진다. 첫 번째 열에 위치하면 만들 수 있..

문제 링크 :: https://www.acmicpc.net/problem/11659 Solution 아주 아주 기본적이고 쉬운 구간 합 문제. 부분 합을 구해 놓고 시키는 대로 구간 합을 구하면 된다. 괜히 배열의 크기를 딱 문제에 제시된 수열의 최대 크기만큼만 선언하지 말고, 한 칸만 더 선언해 준 다음에 인덱스와 주어지는 구간을 일치시키는 게 훨씬 직관적이고 편하다. 수열을 이루는 숫자는 작아도 더하면 좀 커지므로 데이터 타입을 더 큰 단위로 선언해 주는 게 좋다. 물론 이 문제에서는 100000개의 숫자가 모두 1000이고 처음부터 끝까지의 합을 구해도 int형 범위 내일 것 같긴 한데, 넘어가는 문제도 많으니까. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..

문제 링크 :: https://www.acmicpc.net/problem/1806 Solution 문제 이름처럼 부분 합을 이용해서 푸는 문제. 그래서 일단 sum 배열에 부분 합을 구해 줬다. 그리고 나서는 어떻게 시간 초과가 나지 않으면서 합이 S 이상인 구간 합 중 가장 길이가 짧은 것을 구하느냐가 관건이었다. 다른 사람들은 어떻게 풀었는지 모르겠지만 나는 S 이상의 부분 합이 나타나는 부분 합을 발견하면 그 인덱스를 기준으로 가장 짧은 구간 합(j가 i-1인 경우)부터 계산하면서 그 값이 S 이상이 되면 정답 후보 배열(sol)에 길이를 저장해 주도록 했다. 가장 짧은 구간 합부터 구하니까 S 이상인 값을 발견하면 바로 반복문을 탈출한다. 만약 가장 짧은 구간 합이 S 이상이면 굳이 나머지 구간 ..

문제 링크 :: https://www.acmicpc.net/problem/10951 Solution 매우 간단한 문제입니다. 다만 테스트 케이스의 개수도 주어져 있지 않고 종료 조건도 명시되어 있지 않아 데이터를 더 이상 읽을 수 없음을 나타내는 EOF(End Of File, 콘솔에서는 ctrl+Z로 입력 가능)가 나올 때까지 데이터를 계속 입력받아야 합니다. 혹은 scanf가 반환하는 값이 2인 경우에만 반복문 블럭을 수행하도록 할 수도 있습니다. scanf는 포맷 형식의 수를 반환합니다. 에러가 발생하거나 EOF를 만나면 -1을 리턴합니다. Code 1 2 3 4 5 6 7 8 9 #include int main(void) { int a, b; while (scanf("%d %d", &a, &b) !..