본문 바로가기

알고리즘346

[백준 14246] K보다 큰 구간 (C++) https://www.acmicpc.net/problem/14246문제 n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j] (i≤j)의 합이 k보다 큰 모든 쌍 (i,j)의 개수를 출력하시오.입력첫째 줄에는 자연수의 개수 n이 주어진다. (1 ≤ n ≤ 100000)다음 줄에는 자연수 n개가 주어진다. 자연수는 100,000보다 크지 않다.그 다음 줄에는 자연수 k가 주어진다. (1 ≤ k ≤ 1,000,000,000) 출력특정 구간 [i,j]의 합이 k보다 큰 모든 쌍 (i,j)의 개수를 출력하시오. 문제 풀이투 포인터 문제. 주어진 수가 모두 자연수이므로 [i, j]가 k보다 크다면 j보다 큰 모든 수 l에 대해 [i, l]이 k보다 크다. 이를 이용하여 투포인터를 사용하여 i(=투포인.. 2024. 12. 19.
[백준 15723] n단 논법 (C++) https://www.acmicpc.net/problem/15723문제모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.지무근은 중앙대 컴퓨터공학부 학생이다.그러므로 지무근은 미인이다.위 연역 논증은 대표적인 삼단논법의 예시이다. 삼단논법이란 전제 두 개와 결론 하나로 이루어진 연역 논증이다. 이것을 응용하면, n개의 전제가 있을 때 m개의 결론을 도출할 수 있을 것이다. 이때의 n과 m은 모든 의미에서 적절한 수라고 가정하자. 자세한 것은 입출력 예시를 확인하자. 입력첫째 줄에 정수 n(2 ≤ n ≤ 26)이 주어진다.둘째 줄부터 n개의 줄에 걸쳐 각 줄에 전제가 하나씩 주어진다. 전제는 모두 a is b의 형식으로 주어지며 a와 b는 서로 다른 임의의 알파벳 소문자이다. 특별한 명시는 없지만.. 2024. 12. 18.
[백준 1821] 수들의 합 6 (C++) https://www.acmicpc.net/problem/1821문제가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.3 1 2 4 4 3 6 7 9 16N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러 가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. 입력첫째 줄에 두개의 정수 N(1 ≤ N ≤ 10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,00.. 2024. 12. 17.
[백준 17503] 맥주 축제 (C++) https://www.acmicpc.net/problem/17503문제내일부터 N일 동안 대구광역시에서 맥주 축제가 열립니다!이 축제에서는 무려 K종류의 맥주를 무료로 제공합니다.축제 주최자는 축제에서 더 많은 참가자들이 다양한 종류의 맥주를 즐겼으면 합니다. 그래서 축제에서 참가자들은 하루에 맥주 1병만 받을 수 있고, 이전에 받았던 종류의 맥주는 다시 받을 수 없습니다.맥주를 정말로 사랑하는 대학생 전씨는 무료 맥주 소식에 신이 났습니다. 전씨는 이 맥주 축제에 참가해 총 N일 동안 맥주 N병을 마시려 합니다.하지만 전씨에게는 큰 고민이 있었습니다. 전씨는 맥주를 사랑하지만, 도수가 높은 맥주를 마시면 기절하는 맥주병이 있습니다. 전씨는 맥주를 마시다 기절하면 늦잠을 자 다음 날 1교시 수업에 결석해.. 2024. 12. 16.
[백준 28449] 누가 이길까 (C++) https://www.acmicpc.net/problem/28449문제HI-ARC는 종강을 맞아 HI팀과 ARC팀으로 나누어 친선대회를 열려고 한다. HI팀엔 N명 ARC팀엔 M명이 속해있다. 대회는 다른 팀끼리 모든 사람들끼리 한번씩 대결을 하는 것으로, 대회는 N×M개의 대결로 이루어진다. 모든 참가자는 코딩실력을 가지고 있다. 대결을 하면 더 높은 코딩실력을 가진 참가자가 승리하고, 두 참가자의 코딩실력이 같다면 무승부가 된다.하얔이는 이 대회의 결과를 빨리 알고싶어졌다. 하얔이를 위해 대회의 결과를 예측해보자! 입력첫째 줄에 HI팀의 인원 수 N, ARC팀의 인원 수 M이 공백으로 구분되어 정수로 주어진다. (1 ≤ N,M ≤ 100000)둘째 줄에 HI팀의 참가자의 코딩실력을 나타내는 길이 N .. 2024. 12. 15.
[백준 27277] 장기자랑 (C++) https://www.acmicpc.net/problem/27277문제즐거운 설날을 맞아 부대 장기자랑 행사가 개최된다! 이 행사는 한 번에 한 명씩 순서대로 공연하는 형식으로 진행된다.장기자랑 행사의 총관리자는 공연하는 병사들의 장기자랑 실력을 토대로 행사를 준비하던 중, 아무래도 앞에 공연한 사람이 너무 잘하면 뒤에 공연하는 사람이 부담감을 느껴 본 실력을 발휘하지 못할 것이라는 고민을 하게 되었다. 이에 총관리자는 각 병사의 장기자랑 실력을 순서대로 a1,a2,⋯,an이라고 할 때, 2 ≤ i ≤ N에 대하여 i번째 공연자는 실력을 max(0,ai−ai−1)만큼만 발휘할 수 있을 것이라는 가설을 세웠다. 이때, 가장 먼저 공연하는 병사는 본인의 실력을 그대로 발휘할 수 있다.위 가설에 따라, 총관리.. 2024. 12. 14.
[백준 9328] 열쇠 (C++) https://www.acmicpc.net/problem/9328문제상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며.. 2024. 12. 13.
[백준 10872] 팩토리얼 (C++) https://www.acmicpc.net/problem/10872문제0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. 입력첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다. 출력첫째 줄에 N!을 출력한다. 문제 풀이dp 혹은 재귀를 이용하는 문제. N이 12까지이므로 dp나 재귀 어느쪽을 사용해도 된다. dp는 작은 수부터 계산하고 해당 값을 저장하여 이전에 저장한 값을 이용하며, 재귀는 N부터 숫자를 줄여나가며 이후에 구해질 값에 숫자를 곱하는 방식으로 구현된다. 아래는 코드.더보기#include using namespace std;long long fac(int N){ if (N > N; cout 2024. 12. 12.
[백준 6588] 골드바흐의 추측 (C++) https://www.acmicpc.net/problem/6588문제1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.이 추측은 아직도 해결되지 않은 문제이다.백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.각 테스트 케이스는.. 2024. 12. 11.

티스토리툴바