본문 바로가기

분류 전체보기378

[백준 30802] 웰컴 키트 (C++) https://www.acmicpc.net/problem/30802문제2024년 2월 3일 개최 예정인 온사이트 그랜드 아레나에서는 참가자들에게 티셔츠 한 장과 펜 한 자루가 포함된 웰컴 키트를 나눠줄 예정입니다. 키트를 제작하는 업체는 다음과 같은 조건으로만 주문이 가능합니다.티셔츠는 S, M, L, XL, XXL, 그리고 XXXL의 6가지 사이즈가 있습니다. 티셔츠는 같은 사이즈의 𝑇장 묶음으로만 주문할 수 있습니다.펜은 한 종류로, 𝑃자루씩 묶음으로 주문하거나 한 자루씩 주문할 수 있습니다.총 𝑁명의 참가자 중 S, M, L, XL, XXL, XXXL 사이즈의 티셔츠를 신청한 사람은 각각 𝑆, 𝑀, 𝐿, 𝑋𝐿, 𝑋𝑋𝐿, 𝑋𝑋𝑋𝐿명입니다. 티셔츠는 남아도 되지만 부족해서는 .. 2024. 7. 18.
[백준 28464] Potato (C++) https://www.acmicpc.net/problem/28464 문제감자튀김을 좋아하는 박 모 씨와 다르게, 성우는 감자튀김을 그렇게 좋아하지는 않는다. 어느 날 박 모 씨와 성우는 수많은 감자튀김을 받게 되었고, 이를 나누어 가지기로 했다.책상 위에 𝑁개의 접시가 놓여있다. 𝑖번째 접시에는 𝑎𝑖개의 감자튀김이 있다. 박 모 씨와 성우는 다음 행동을 번갈아 시행한다.책상 위에 남아있는 접시 하나를 고르고, 접시와 그 위에 놓인 모든 감자튀김을 가져간다.이는 책상 위의 접시가 모두 사라질 때까지 반복한다. 맨 처음 접시를 가져가는 사람은 박 모 씨다.박 모 씨는 가져가는 감자튀김의 양을 최대화하려 하고, 성우는 가져가는 감자튀김의 양을 최소화하려 한다. 두 사람이 항상 최선의 행동을 한다고 가정.. 2024. 7. 17.
[백준 17216] 가장 큰 감소 부분 수열 (C++) https://www.acmicpc.net/problem/17216문제수열 A가 주어졌을 때, 그 수열의 감소 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 합이 가장 큰 감소 부분 수열은 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 이고, 합은 186이다. 입력 첫째 줄에 수열 A의 크기 N(1 ≤ N ≤ 1000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다.(1 ≤ Ai ≤ 1,000) 출력첫째 줄에 수열 A의 합이 가장 큰 감소 부분 수열의 합을 출력한다. 문제 풀이LIS 알고리즘.일반적인 LIS 알고리즘에서는 dp 배열에 증가하는 형태이.. 2024. 7. 16.
[백준 15565] 귀여운 라이언 (C++) https://www.acmicpc.net/problem/15565문제꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라. 입력첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 106)둘째 줄에 N개의 인형의 정보가 주어진다. (1 또는 2) 출력K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력한다. 문제 풀이투포인터 슬라이딩 윈도우 문제.처음 시작할 때 배열의 인덱스를 나타내는 start와 end를 각각 0으로 설정하고, start를 증가시키며 라이언 인형의 개수가 K가 될 .. 2024. 7. 15.
[백준 1456] 거의 소수 (C++) https://www.acmicpc.net/problem/1456문제어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력첫째 줄에 총 몇 개가 있는지 출력한다. 제한1 ≤ A ≤ B ≤ 1014 문제 풀이에라토스테네스의 체를 활용한 문제. sqrt(B)를 초과하는 수에 대해서는 2제곱의 값이 B를 넘어가므로 거의 소수가 존재하지 않는다. 따라서 sqrt(B)까지의 소수들을 에라토스테네스의 체를 이용해 구해 벡터에 저장한다.모든 소수들을 구했다면 벡터의 각 원소(=소수)들에 대해 A와 B .. 2024. 7. 14.
[백준 20166] 문자열 지옥에 빠진 호석 (C++) https://www.acmicpc.net/problem/20166문제하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자.너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸.. 2024. 7. 13.
[백준 1707] 이분 그래프 (C++) https://www.acmicpc.net/problem/1707문제그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인.. 2024. 7. 12.
[백준 16967] 배열 복원하기 (C++) https://www.acmicpc.net/problem/16967문제크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐진다.즉, 배열 B의 (i, j)에 들어있는 값은 아래 3개 중 하나이다.(i, j)가 두 배열 모두에 포함되지 않으면, Bi,j = 0이다.(i, j)가 두 배열 모두에 포함되면, Bi,j = Ai,j + Ai-X,j-Y이다.(i, j)가 두 배열 중 하나에 포함되면, Bi,j = Ai,j 또는 Ai-X,j-Y이다.배열 B와 정수 X, Y가 주어졌을 때, 배열 A를 구해보자. 입력첫째 줄에 네 정수 H, W, X.. 2024. 7. 11.
[백준 7453] 합이 0인 네 정수 (C++) https://www.acmicpc.net/problem/7453문제정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력합이 0이 되는 쌍의 개수를 출력한다. 문제 풀이MITM 알고리즘과 투포인터를 같이 사용하는 문제.A, B, C, D 4개 배열을 모든 A+B를 저장하는 벡터 v1, 모든 C+D를 저장하는 벡터 v2 2개로 만들어 시간 복잡도를 줄인다. 벡터를 사용해 .. 2024. 7. 10.

티스토리툴바