목록2025/09 (27)
넘치게 채우기
https://www.acmicpc.net/problem/27232BOJ - 청소문제 유형: 집합, 슬라이딩 윈도우문제 난이도: Gold I시간 제한: 2초메모리 제한: 1024MB 문제준석이는 청소 업체에 다니고 있다. 준석이가 청소할 장소는 1번부터 N번까지 차례로 번호가 붙은 일렬의 1N개의 구역으로 나누어져 있다. i번 구역은 i-1번과 i+1번 구역과 인접해 있어, 두 인접한 구역 사이를 이동하려면 1만큼 걸어야 한다.각 구역에는 우선순위가 있다. i번 구역의 우선순위 A_i는 1이상 N이하의 정수로 이 값이 클수록 우선순위가 높다. 임의의 두 구역의 우선순위는 항상 다르다.준석이는 오늘 이 구역 중 K개의 구역을 먼저 청소하려고 한다. 단, 준석이가 청소하는 K개의 구역은 반드시 연속해야 한다..
https://www.acmicpc.net/problem/3217BOJ - malloc문제 유형: 구현, 집합과 맵(set, map), 문자열 처리문제 난이도: Gold I시간 제한: 1초메모리 제한: 128MB 문제메모리 할당 명령을 시뮬레이팅하는 프로그램을 작성하시오.메모리는 100,000개의 연속된 공간이고, 1번부터 100,000번까지 번호가 매겨져 있다. 초기에 모든 공간은 할당되지 않은 상태이다.명령어의 종류는 다음 중 하나이다.var=malloc(size);이 함수은 처음 등장하는 size개의 연속된 공간을 찾아, 할당해주는 함수이다. 이 함수의 리턴값은 할당된 공간의 제일 처음 주소이다. 만약, 할당해줄 수 있는 공간이 없다면 0을 리턴한다. (100 ≤ size ≤ 100,000)free..
https://www.acmicpc.net/problem/12004BOJ - Closing the Farm문제 유형: bfs/dfs, 그래프문제 난이도: Gold IV시간 제한: 2초메모리 제한: 512MB 문제Farmer John and his cows are planning to leave town for a long vacation, and so FJ wants to temporarily close down his farm to save money in the meantime.The farm consists of N barns connected with M bidirectional paths between some pairs of barns (1 ). To shut the farm down, FJ ..
https://www.acmicpc.net/problem/1263BOJ - 시간 관리문제 유형: 정렬, 그리디문제 난이도: Gold V시간 제한: 2초메모리 제한: 128MB 문제진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.진영이가 바라..
https://www.acmicpc.net/problem/30190BOJ - 여우의 꿈문제 유형: 수학, 그리디, 재귀문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제여우 마을에는 3개의 기둥과 N개의 원판을 가진 하노이 탑의 원판들을 한 곳에 모으면 소원이 이루어진다는 전설이 있다.하노이 탑의 원판들을 이동시키는 규칙은 다음과 같다.i번째 원판의 반지름은 i이다. (1 )어떤 시점에라도 한 기둥 안의 원판은 반지름이 작을수록 위로 오도록 정렬되어 있어야 한다.각 기둥의 제일 위에 있는 원판만 이동할 수 있다.원판은 기둥의 맨 위로만 이동할 수 있다.원판은 한 번에 한 개만 이동할 수 있다.여우 마을에 사는 아기 여우는 어느 날 이 소문을 듣고 하노이 탑에 도전하기로 했다. 아기 ..
https://www.acmicpc.net/problem/2938BOJ - 3으로 나누어 떨어지지 않는 배열문제 유형: 애드 혹, 해 구성하기, 많은 조건 분기문제 난이도: Gold V시간 제한: 1초메모리 제한: 256MB 문제자연수로 이루어진 배열이 주어졌을 때, 수의 순서를 적절히 바꿔서 인접한 두 수의 합이 3으로 나누어 떨어지지 않는 배열을 만드는 프로그램을 작성하시오. 입력첫째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 10000)둘째 줄에는 배열에 들어있는 수가 공백으로 구분되어 주어진다. 수는 1,000,000보다 작거나 같은 자연수이다. 출력만약, 3으로 나누어 떨어지지 않게 배열을 만들 수 있다면 첫째 줄에 출력한다. 불가능하다면 -1을 출력한다. 풀이0을 나머지가 0인 수들, ..
https://www.acmicpc.net/problem/17255BOJ - N으로 만들기문제 유형: 브루트 포스, 백트래킹문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제준하는 노트에 수를 적다가 수가 만들어지는 방식을 깨달았다.처음에 어떤 숫자 하나를 적고 만들어진 수의 왼쪽이나 오른쪽에 숫자를 계속 붙이면 어떤 수 N이든 만들 수 있다는 것이다.다시 말해 어떤 수 N을 만들기 위해서는, 처음에 어떤 숫자를 하나 적고 아래의 두 가지 행동을 반복한다.수의 왼쪽에 숫자를 하나 적는다.수의 오른쪽에 숫자를 하나 적는다.준하는 어떤 수 N을 만드는 방법의 수가 몇 가지인지 궁금해졌다. 이를 알아내는 프로그램을 작성해주자. 숫자를 적는 과정에서 나온 수가 순서대로 모두 같다면 같은 방..
https://www.acmicpc.net/problem/19646BOJ - Random Generator문제 유형: 세그먼트 트리, 이분 탐색문제 난이도: Platinum V시간 제한: 1초메모리 제한: 1024MB 문제국렬이는 1부터 N까지의 양의 정수로 이루어진 순열을 주어진 양의 정수 w1 ... , wN를 이용해서 무작위로 만들 것이다. 다음은 무작위로 순열을 만드는 방법이다.1부터 N까지의 양의 정수 i (1 ≤ i ≤ N)를 연속적으로 wi개씩 배치한다.현재 배치된 양의 정수의 총 개수를 W라고 하자. 1부터 W까지의 양의 정수들 중에서 균등하게 숫자 하나 pi를 선택한다.pi번째 수를 순열에 추가한다.순열에 추가한 수들을 전부 지우고, 남은 수가 없을 때까지 2부터 4의 과정을 거친다.w1..
https://www.acmicpc.net/problem/30867BOJ - 과제가 너무 많아요문제 유형: 문자열, 애드 혹문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제과제가 너무 많은 로하는 과도한 두통에 시달리며 영어 단어에 있는 모든 wh를 hw로 보게 되었다! 두통이 한번 올 때마다, 문자열 $S$는 다음의 시행에 따라 변화한다. 문자열 S는 1번째 글자부터 L번째 글자까지 있는 길이 L의 문자열이다.문자열 S의 i=1번째 글자부터 L-1번째 글자까지, 다음 과정을 반복한다.만약 i번째 글자와 i+1번째 글자가 차례로 w와 h라면, i번째 글자와 i+1번째 글자를 각각 h와 w로 바꾼다.로하가 N번의 두통을 겪고 나서 주어진 문자열을 어떤 문자열로 보게 될지 출력하여..
https://www.acmicpc.net/problem/2259BOJ - 두더지 잡기문제 유형: 다이나믹 프로그래밍, 정렬문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제정은이는 두더지 잡기 게임을 즐겨 한다. 어느 날 정은이는 한 야외 행사에서 대형 두더지 잡기 게임을 하게 되었다.게임은 큰 벌판에서 진행되는데, 게임을 시작한 뒤 T(1 ≤ T ≤ 1,000,000,000)초가 지났을 때, 벌판의 (x, y) 좌표(0 ≤ |x|, |y| ≤ 1,000)에서 두더지가 나타나게 된다. 두더지는 매우 짧은 시간동안만 나타나므로, 정확히 T초에 그 위치에 있게 되면 그 위치에서 나타나는 두더지를 잡을 수 있다. 게임을 하기 위해서는 벌판의 이곳저곳을 돌아다녀야 하는데, 정확히 T초에..