본문 바로가기

Algorithm Problems

 (212)
[백준/C++] 10986번: 나머지 합 문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제 요약 N개의 이루어진 수열 A의 연속된 부분 수열의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 코드 ??? 코드 설명 0 ~ i 까지의 누적합 => prefix[i] 부분 수열 (i + 1~ j) 의 합 => prefix[j] - prefix[i] 부분 수열 (i + 1 ~ j) 의 합이 M으로 나뉜다. => (prefix[j]..
[백준/C++] 2042번: 구간 합 구하기 문제 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 요약 N개의 수가 배열 A에 저장되어 있다. 중간에 A[i]의 변경이 빈번히 일어날 때, 어떤 부분의 합을 구하려고 한다. 코드 #include #include #define ll long long #define MAX_N 1000000 using namespace std; ll n, m, k; ll A[MAX_N + 1]; l..
[백준/C++] 13335번: 트럭 문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제 요약 강을 가로지르는 하나의 차선으로 된 다리가 있다. n개의 트럭이 다리를 건너려고 한다. 각 트럭은 무게를 갖고, 다리 위에 있는 트럭들의 무게의 합은 다리의 최대 하중 L보다 작거나 같아야한다. 다리의 길이 w는 단위 길이이고, 트럭들은 단위 시간(1)에 단위 길이(1)만큼 이동할 수 있다. 모든 트럭이 다리를 건너는 시간을 출력한다..
[백준/C++] 2018번: 수들의 합 5 문제 https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 문제 요약 자연수 n을 연속된 자연수들의 합으로 나타내는 가지수를 출력한다. 이 때, 사용하는 자연수는 n이하이다. ex) 15를 나타내는 방법 15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5 코드 #include using namespace std; int n; int main() { cin >> n; int left = 0; int rig..
[백준/C++] 15565번: 귀여운 라이언 문제 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 문제 요약 1과 2로 이루어진 n개의 수열이 주어질 때, 1을 k개 갖는 가장 작은 부분 수열의 길이를 출력한다. 코드 #include #include #define MAX_N 10000 #define INF 1000000000 using namespace std; int n, k; int res = INF; vector lions; // 라이언 인형들의 인덱스 정보 저장 int mai..
[백준/C++] 10844번: 쉬운 계단 수 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 요약 각 자릿수와 인접한 모든 자릿수의 차이가 1인 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 출력한다. + 0으로 시작하는 수는 계단 수가 아니다. 코드 #include #define ll long long using namespace std; int n; ll dp[101][10]; // dp[i][j]: 길이가 i인 계단수 중 j로 끝나는 수의 개수 int main() { cin >> n; // dp 초기값 (길이가 1인 계단 수들) for (int i ..

티스토리툴바