본문 바로가기

플래티넘17

[백준 15678] 연세워터파크 [C++] 풀이 정수 K가 적혀있는 N개의 징검다리에 대해 징검다리를 건너며 얻을 수 있는 최대값을 구하는 문제다. 문제에서 주어진 조건 중 아래와 같은 조건이 있다. N개의 모든 징검다리에 순서대로 1 ~ N의 번호를 붙인다. U번 징검다리에서 V번 징검다리로 점프하기 위해서는, U와 V의 차이가 미리 정해진 값 D 이하여야 한다. 어떤 징검다리도 두 번 이상(한 번을 넘게) 밟을 수는 없다. 때문에, 징검다리의 양 끝이 아닌 중간에서 시작하더라도 왼쪽 또는 오른쪽 방향으로만 진행할 수 있다. 서로 다른 방향이더라도 결국 반대 방향의 부분집합에 속하는 영역이기 때문에 징검다리를 한 방향으로 진행한다고 가정하고 dp로 풀이할 수 있다. 진행 방향은 1번부터 N번이며 D씩 이동한다면 모든 징검다리가 탐색 대상이다. .. 2023. 9. 30.
[백준 28439] 행렬 연산 (연산 찾기) [Python] 풀이 모든 행과 열에 대해 연산을 적용해 입력받은 행렬과 비교하는 방법은 시간초과가 날것이 자명하다. 마치 노노그램 게임처럼 그림을 그리듯 테두리의 행/열 값을 가지고 연산을 하면 풀 수 있는 문제다. 행/열에 더하는 수를 R(i), C(j)라 한다면, 다음을 만족한다. R(i) + C(j) = A(i, j) C(j) = A(i, j) - R(i) = A(1, j) - R(1) R(i) = A(i, j) - C(j) = A(i, 1) - C(1) = A(i, 1) - { A(1, 1) - R(1) } = A(i, 1) - A(1, 1) + R(1) 위와 같은 수식을 통해 행렬을 만들 수 있다. 하지만, 이러한 연산의 횟수를 최소화 해야한다. 아래의 예제를 살펴보자. 위 행렬을 만들기 위해 최대 5번의 연.. 2023. 8. 19.
[백준 28433] 게리맨더링 [Python] 풀이 양수구간의 갯수가 음수구간의 갯수보다 많은지 판별하는 pure greedy 문제이다. 양수/음수구간에 대해 최대 구간을 구하기 위한 조건을 생각해보자. 먼저 양수구간의 경우 두 양수는 각각의 구간을 가지는 것이 좋다. 만약, 음수구간이다가 양수 또는 0을 만났을 경우 해당 구간을 합쳐 양수로 만들어 음수구간의 수를 최소화 할 수 있다면 합쳐야 한다. 음수구간에 대해서는 최대한 음수끼리는 합쳐야 한다. 만약 양수구간이다가 음수 또는 0 을 만났고, 합쳐서 양수구간으로 만들지 못한다면, 분리해야한다. 양수/음수구간의 판단은 이전구간의 합과 현재 요소의 값을 통해 최적으로 판단해야 되기 때문에 합는 경우는 단순히 이전 구간에 현재 구간의 값만 더해준 후 다음으로 넘어가면 된다. 또한, 요소 자체가 0인 .. 2023. 8. 11.
[백준 2104] 부분배열 고르기 [C++] 풀이 일반적으로 범위가 넓을수록 최솟값과의 곱으로 인해 점수가 작을것이다. 때문에, 최솟값을 기준으로 나눈 영역(최솟값을 제외한 나머지 영역)에 대해 점수를 구할 때 높은 점수를 기대할 수 있다. 그러기 위해서는 먼저, 구간별로 가지는 합과, 최솟값을 구해야 한다. leaf를 입력받은 후 초기화를 진행해주자. pair에 합과, 최솟값을 가지는 요소의 index를 넣어줬다. 위에서 언급했듯, 최솟값을 기준으로 나눈 영역의 범위를 설정하기 위해서 value가 아닌 index를 넣어줬다. 구간별로 점수를 계산하기 위해 query를 작성해주었다. 주어진 구간에 대한 합과 최솟값의 index로 이루어진 pair를 반환한다. 초기화 단계에서는 올바르지 않은 요소를 접근하지 않는다. 하지만 위의 query는 올바르지.. 2023. 8. 7.
[백준 18138] 리유나는 세일러복을 좋아해 [Python] 풀이 n개의 티셔츠와 m개의 세일러 카라에 대한 bipertite matching 문제이다. 단, 모든 티셔츠가 모든 세일러 카라에 대한 매칭이 가능한 것이 아니다. 문제에서 주어진 아래의 조건을 만족하는 경우에만 매칭이 가능하다. 하얀 티셔츠의 너비를 정수 w라고 할 때, 여기에 붙일 수 있는 세일러 카라는 두 가지가 있다. 너비가 w/2 이상 w×3/4이하인 세일러 카라를 붙일 수 있다. 카라가 옷보다 살짝 더 넓게 만들어서 너비가 w 이상 w×5/4 이하인 카라를 붙일 수 있다 티셔츠에 대해 입력받은 세일러 카라의 너비를 위의 조건에 맞게 미리 만들어준다면, 티셔츠별로 살펴봐야 하는 불필요한 카라들이 너무 많아진다. 때문에 일단은 너비만 입력받고, 매칭하는 과정에서 위의 너비에 대한 조건을 만족해 .. 2023. 6. 24.
[백준 1298] 노트북의 주인을 찾아서 [Python] 풀이 학생 N명에 대해 고를 수 있는 노트북 최대 N개에 대한 bipartite matching 기본 문제다. 노트북의 번호에 관계없이 최대 N개만 존재하기 때문에 배열을 N에 맞춰 match, visited 배열의 크기를 지정해주자. 소스코드 소스코드 보기 출처 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net 2023. 6. 14.

티스토리툴바