본문 바로가기

공부/알고리즘 문제풀이 기록46

[Codeforces Round #966] E - Photoshoot for Gorillas https://codeforces.com/contest/2000/problem/E알고리즘 : 그리디 1. 문제요약n * m 격자로 표현되는 정글에 w마리의 고릴라들이 있다. 한 격자에는 최대 한마리까지 들어갈 수 있다. 고릴라들의 키가 주어진다. 키를 고려하여 고릴라를 정글 격자에 적절히 배치시킨다.정글에 포함되는 모든 k*k 정사각형 부분마다 고릴라들의 키의 합을 구한다. (k는 n과 m 이하의 값이다)위에서 구한 값들의 합을 최대화하도록 고릴라를 배치할 때, 그 최대값을 출력한다.테스트케이스의 개수 t가 주어지고, 각 테스트케이스마다 첫번째 줄에 n,m,k의 값을, 두번째 줄에 w의 값을, 마지막 줄에 고릴라의 키 배열이 입력으로 주어진다. 입출력 예시는 아래와 같다.2. 아이디어모든 정글 격자에 고.. 2024. 8. 15.
[Codeforces Round #953] C - Manhattan Permutations Problem - C - Codeforces codeforces.com알고리즘 : 그리디, 구현 1. 문제요약1부터 n까지 n개의 수를 적당히 배치한 수열을 $p_1,p_2,...,p_n$이라 하자.Manhattan value란 $|p_1 - 1| + |p_2 - 2| + ... + | p_n - n|$을 말한다.t개의 테스트케이스가 존재한다. 각 테스트케이스마다 n과 k가 주어질때, Manhattan value를 k로 만드는 수열이 존재한다면 'Yes'와 함께 그러한 수열  $p_1,p_2,...,p_n$을 출력한다. 존재하지 않는다면 'No'를 출력한다.예시 입출력은 아래와 같다. 2. 아이디어우선 수열이 1, 2, ..., n이라면 Manhattan value는 0이된다. 여기서 임의의 두 수의 위.. 2024. 7. 12.
[백준 2179] 비슷한 단어 https://www.acmicpc.net/problem/2179알고리즘 : 해시난이도 : 골드Ⅳ 1. 문제요약N개의 영단어가 주어진다. N은 20000이하의 자연수이고 각 영단어는 소문자로 이루어진 100자이내의 단어이다.두 단어를 앞글자부터 확인하여 공통되는 부분의 길이가 길어질 수록 두 단어가 비슷한 정도가 커진다고 하자. 예를들어 abcd와 abecd가 있을때 두 단어를 앞에서부터 보면 ab가 공통된다.N개의 단어에서 가장 비슷한 단어를 출력한다. 단 비슷한 단어가 여러개인 경우 입력이 빠른 순대로 출력한다. 예시입출력은 아래와 같다.2. 아이디어단어를 한쌍씩 일일히 비교하면 $O(N^2)$의 시간복잡도를 갖게되어 단어가 2만개가 주어진다면 시간초과가 된다.시간복잡도 충족을 위해 모든 단어를 앞에.. 2024. 6. 23.
[백준 5525] IOIOI https://www.acmicpc.net/problem/5525알고리즘 : 문자열난이도 : 실버Ⅰ 1. 문제요약IOI, IOIOI, IOIOIOI와 같이 I와 O가 번갈아가며 등장하는 문자열 P가 있다. P는 N+1개의 I와 N개의 O로 이루어져 있고, 여기서 N은 1,000,000이하의 자연수이다.I와 O로만 이루어진 길이 M인 문자열 S가 주어진다. M은 2N+1 이상 1,000,000이하의 자연수이다.S에 P가 몇 군데 포함되어 있는지 구하는 프로그램을 작성해보자. N, M, S를 입력받으면 P의 포함 개수를 출력하면 된다. 예시 입출력은 아래와 같다.2. 아이디어실버치고 생각보다 어려웠던 문제였다. 문자열 S의 모든 문자들을 일일히 확인하는 간단한 알고리즘을 생각할 수 있으나 약 O(N*M)의 .. 2024. 6. 14.
[백준 14503] 로봇 청소기 https://www.acmicpc.net/problem/14503알고리즘 : 구현, 시뮬레이션난이도 : 골드Ⅴ 1. 문제요약N * M 크기의 방이 주어진다. 값이 0인 경우 청소되지 않은 빈 칸이고, 1인 경우 벽이 있는 곳이다.로봇청소기는 다음과 같이 동작한다.현재 칸이 청소되지 않았다면 현재 칸을 청소한다.move1 : 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없다면 바라보는 방향을 유지한 채로 후진이 가능하면 한 칸 후진하고, 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.move2 : 주변 4칸 중 청소되지 않은 빈 칸이 있다면 청소되지 않은 빈칸을 마주할때까지 반시계 방향으로 90도씩 회전하고, 청소되지 않은 칸으로 전진한다.입력으로 방의 크기 N, M이 첫째 줄에 주어지고, 둘째줄.. 2024. 5. 15.

티스토리툴바