본문 바로가기

Problem Solving

 (8)
[BOJ] 18186 라면 사기 (Large) https://www.acmicpc.net/problem/18186  한 수열이 주어졌을 때, 해당 수열의 임의의 위치에서 {1}, {1, 1}, {1, 1, 1}를 여러 번 제거하여 해당 수열의 원소를 모두 0으로 만드는 문제. 단, 제거하는 비용은 문제에 주어진 규칙에 따라야 한다.  1/ 조건1) 수열의 길이 N과 비용을 구성하는 숫자 B, C, 수열의 원소 A_i가 주어진다. 입력 제한은 다음과 같다:    ●  3 ≤ N ≤ 10^6     ●  1 ≤ B ≤ 10^6     ●  1 ≤ C ≤ 10^6     ●  0 ≤ A_i ≤ 10^6 (1 ≤ i ≤ N)2) 수열의 제거 연산 - 즉 라면 구매는 다음과 같은 3가지의 방법만 존재한다:    (1) i번 공장에서 라면을 하나 구매한다(1 ..
[BOJ] 17299 오등큰수 https://www.acmicpc.net/problem/17299  한 수열이 주어졌을 때, 각 원소에 대하여, 해당 원소보다 등장빈도가 높은 숫자 중 오른쪽 방향으로 가장 가까이에 있는 숫자를 구하는 문제.  1/ 조건1) 수열의 크기는 1 이상 100만 이하다.2) 각 원소의 크기는 1 이상 100만 이하다.3) 시간 제한은 1초, 메모리 제한은 512MB.  2/ 설계일단 메모리가 충분하므로 100만+1의 크기를 갖는 배열을 만들어서 등장빈도를 기록해야겠다고 생각했다. 그렇게 해야 O(1)으로 각 등장빈도를 호출할 수 있을 테니.가장 간단한 방식은 각 원소보다 큰 인덱스를 탐색하며 등장빈도가 높은 원소를 만나면 break를 하는 것인데, 최악의 경우(예를 들어 모든 원소가 한 번만 등장할 경우) ..
[BOJ] 1695 팰린드롬 만들기 https://www.acmicpc.net/problem/1695  한 수열이 주어졌을 때, 주어진 수열을 팰린드롬(palindrome, 회문)으로 만들기 위해 추가해야 하는 숫자의 최소 개수를 구하는 문제.  1/ 조건1) 첫째 줄에 수열의 길이 n이 주어진다. 1 2) 수열을 이루는 숫자 n개가 주어진다. 각 숫자는 -2^31 이상 2^31 미만이다.  2/ 설계숫자를 어떤 식으로 추가해야 짝을 맞출 수 있을까에 대해 고민하다가 숫자를 추가하는 것과 제거하는 것이 동등하다는 사실을 깨달았다. 재귀적으로 하나씩 제거한 결과가 회문인지를 검사하려고 했는데, 그 과정에서 중복된 결과가 얻어졌다. DP 문제라고 생각했다.일단 top-down으로 풀어봤는데 메모리 초과가 났다. 재귀 횟수도 문제지만 메모이제이..
[BOJ] 1799 비숍 https://www.acmicpc.net/problem/1799 주어진 체스판 위에서 비숍을 최대 몇 개까지 둘 수 있는지 세는 문제.  1/ 조건1) 입력 첫 줄에는 정사각형 체스판의 크기 n이 주어진다. 1 2) n*n 행렬이 주어진다. 각 원소가 1이면 해당 위치에는 비숍을 둘 수 있고, 0이라면 둘 수 없다.  2/ 설계당연하게도 바로 DFS를 썼다. 정확히는 백트래킹. 가지치기를 생각할 수 있는 데까지 해봤지만 n=10에서 모든 칸에 비숍을 둘 수 있는 경우를 해결하긴 어려웠다.나는 'n이 정해지면 비숍의 최대치가 정해지는가?'라는 질문에 대해 생각했다. 답은 2n-2. 엄밀한 증명을 통해 얻어낸 것은 아니지만 확신은 있었다.대략적인 추론 과정은 이렇다. n*n 행렬에 존재할 수 있는 대각선은..
[BOJ] 1655 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 이제까지 입력된 숫자 중 중앙값을 출력하는 문제. 1/ 조건 1) 여러 개의 정수가 입력된다. 수가 입력될 때마다 그때까지 입력된 수 중에서 중앙값을 출력해야 한다. 만약 입력된 수가 2k(단, k는 자연수)개라면 k번째로 큰 수를 출력해야 한다. 2) 입력 첫 줄에는 입력되는 수의 갯수 n이 주어진다. 1 secondHalf.element()) { maxVal = firstHal..
[BOJ] 5525 IOIOI https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 1/ 조건 1) P_N은 I로 시작하여 I와 O가 번갈아가며 나오며 2N+1의 길이를 갖는 문자열이다. 2) I와 O로만 이루어진 문자열 S와 정수 N이 이주어졌을 때, S 안에 P_N이 몇 개 포함되어 있는지 구해야 한다. 2/ 설계 시간 제한에 대한 감이 오지 않았다. 일단 순회를 반복하는 방식으로 풀어보고자 했다. 구체적으로..
[BOJ] 10971 외판원 순회 2 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 모든 도시를 한 번씩만 순회하여 시작 도시로 돌아오는 비용의 최소값을 구하는 문제. 1/ 조건 1) 도시의 숫자는 2~10. 2) [임의의 시작 도시 -> (시작 도시를 제외한 모든 도시를 한 번씩) -> 시작 도시]의 구조. 3) adj_matrix[i][j]와 adj_matrix[j][i]의 값은 다를 수 있다. 4) 길이 놓이지 않은 도시는 그 비..
[BOJ] 17070 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 주어진 지형 위에서 파이프를 목적지로 옮길 수 있는 가짓수를 세는 문제. 1/ 조건 1) 파이프는 연속된 2칸을 차지하며, (1, 1)과 (1, 2)에 가로로 놓여 있는 채로 시작한다. 2) 파이프를 (n, n)으로 밀어서 옮겨야 한다. 3) 파이프는 회전시킬 수 있는데, 가능한 방향은 x축을 기준으로 시계방향 0도, 45도, 90도이다. 4) 지형은 0과 1로 주어지는데..

티스토리툴바