노래부르다

1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제분석 N개의 배열 중, 어떤 숫자를 n이라 할 때, 다른 수 '두' 개의 합으로 나타낼 수 있는 '좋은' 수의 개수를 찾는 문제이다. 문제를 보면 두 수의 합이 n과 같은 경우의 수만 찾으면 된다고 생각하지만... 중요한 포인트는 2개이다. 1. 배열의 원소는 중복될 수 있다. 그리고 수의 위치가 다르면 값이 같아도 다른 수이다. 2. '두' 개의 합으로 목표의 숫자를 만들어야 한다. 1. 배열의 원소 중복 예를 들어서, [1 2 3 3 3 4 5]의 배열이 있다고 가정하자. 첫번째 3..

1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 분석 N개의 갑옷 재료 중, 두개의 조합으로 M을 만드는 문제이다. 투 포인터를 사용하여, 원소 두 개의 조합이 목표로 하는 숫자가 되는가를 확인하면 되는 문제이다. 문제 풀이를 총 2가지를 가져왔다. 투포인터를 이용한 풀이와 그렇지 않은 풀이이다. 투 포인터에 대해 알고싶다면 아래 링크로 공부해보자. [Algorithm] 투 포인터(two pointer) 완.전.정.복 투 포인터(two pointer)란? - 투 포인터란, 배열에..

10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제 분석 위 문제는 배열의 모든 조합이 M에 대해 나누어 떨어지는가에 대해 묻고있다. 처음 문제를 접했을 때, 구간 합에 대한 개념을 알고 있다면 쉽게 풀 수 있다는 생각이 드는 문제이다. 구간 합을 모르는 사람이라면, 아래 링크를 통해 공부하고 오길 바란다. 백준 11660번 구간 합 구하기5 (C++) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ ..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 분석 문제는 2차원 배열안에서 (x1,y1) 에서 (x2, y2)의 합을 구하는 문제이다. 원소 하나하나를 더하기보다, 구간마다의 합을 더해서 연산의 속도를 최대한 빠르게 하는 것이 포인트. 즉, 구간 합에 대해 알고 있어야 하는 문제이다. 구간 합이란? 합 배열 S의 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] (A[0]부터 A[i]까지의 합) 이라고 할 때, 합 배열..