본문 바로가기

J 바로가기

🔥 PS(Problem Solving) 🔥/BOJ65

[BOJ] #1522 문자열 교환 시간 제한 메모리 제한 정답 비율 2 초 128 MB 43.590% 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 문제 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다. 예를 들어, aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다. 첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 1,000이다. 첫째 줄에 필요한 교.. 2021. 3. 5.

[BOJ] #3653 영화 수집 시간 제한 메모리 제한 정답 비율 1 초 256 MB 43.106% 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 문제 상근이는 영화 DVD 수집가이다. 상근이는 그의 DVD 콜렉션을 쌓아 보관한다. 보고 싶은 영화가 있을 때는, DVD의 위치를 찾은 다음 쌓아놓은 콜렉션이 무너지지 않게 조심스럽게 DVD를 뺀다. 영화를 다 본 이후에는 가장 위에 놓는다. 상근이는 DVD가 매우 많기 때문에, 영화의 위치를 찾는데 시간이 너무 오래 걸린다. 각 DVD의 위치는, 찾으려는 DVD의 위에 있는 영화의 개.. 2021. 2. 17.

[BOJ] #2042 구간 합 구하기 시간 제한 메모리 제한 정답 비율 2 초 256 MB 23.830 % 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 해결 key point, 세그먼트 트리 2021/02/15 - [🔥 PS(Problem Solving) 🔥/BOJ] - [BOJ] #10868 최솟값 2021/02/15 - [🔥 PS(Problem Solving) 🔥/BOJ] - [BOJ] #11505 구간 곱 구하기 위의 두 문제와 방식은 동일하지만 이 문제는 구간의 합을 구하.. 2021. 2. 15.

[BOJ] #11505 구간 곱 구하기 시간 제한 메모리 제한 정답 비율 1 초 256 MB 33.686 % 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 해결 key point, 세그먼트 트리, '최솟값'과 방식 동일 2021/02/15 - [🔥 PS(Problem Solving) 🔥/BOJ] - [BOJ] #10868 최솟값 위에 보이는 최솟값 문제와 방법은 동일하나 구간의 곱을 구해야 하는 문제이다. 따라서, 초기화를 따로 해줄 필요가 없고, update 함수에서 seg[i].. 2021. 2. 15.

[BOJ] #10868 최솟값 시간 제한 메모리 제한 정답 비율 1 초 256 MB 47.180% 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1,.. 2021. 2. 15.

[BOJ] #1509 팰린드롬 분할 시간 제한 메모리 제한 정답 비율 2 초 128 MB 46.610% 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 해결 key point, '팰린드롬?' 문제를 활용, d[i]는 i번째까지 문자열의 팰린드롬 분할 최솟값. DP j번째 부터 i번째까지 팰린드롬인지 아닌지를 저장한 배열 c[j][i]를 활용해서 → 팰린드롬? 문제 활용 j~i까지의 문자열이 팰린드롬이라면 → c[j][i] == true d[i]는 d[j - 1] + 1이다.. 2021. 2. 9.

[BOJ] #10942 팰린드롬? 시간 제한 메모리 제한 정답 비율 0.5 초 256 MB 28.087% 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 해결 key point, 길이가 1, 2, ... N 까지 팰린드롬인지 확인한다. DP 길이가 1일 때는 모두 팰린드롬 길이가 2일 때는 i, j 양 끝이 같아야 팰린드롬 길이가 3이상일 때는 i, j 양 끝이 같으면서 dp[i+1][j-1]이 true이면 팰린드롬이다. 코드(재귀) 메모리 시간 17664 KB 300 ms 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2.. 2021. 2. 9.

[BOJ] #2632 피자판매 시간 제한 메모리 제한 정답 비율 2 초 128 MB 36.331 % 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 문제 해결 key point, 원형, 누적합, 부분합, 완전탐색 배열 크기 유의하기. 처음에 배열을 작게 잡아서 계속 시간초과가 났었다. → 5번 줄 피자가 원형이기 때문에 `왼→오` 방향으로 누적합을 구하고, `오→왼` 방향으로도 누적합을 구한다. → 13, 19번 줄 부분 합을 구할 때는 j를 `i + n - 1` 이전까지 반복한다. → 23, 38번 줄 실제 sumA,.. 2021. 2. 5.

[BOJ] #1208 부분수열의 합 2 시간 제한 메모리 제한 정답 비율 1 초 256 MB 21.446 % 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값.. 2021. 2. 4.

이전 1 2 3 4 ··· 8 다음

티스토리툴바