본문 바로가기

프로그래밍/PS

 (80)
[C++] 백준 13460번: 구슬 탈출 2 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 시뮬레이션과 너비 우선 탐색을 통해 문제를 풀어볼 것이다. 보드의 정보가 입력된다. R은 빨간공, B는 파란공, O는 목적지를 나타내며 #은 벽을 나타낸다. 먼저, 이러한 정보를 어떻게 효율적이고 깔끔하게 다룰 수 있을지 고민해보자. 클래스를 하나 정의하여 사용해보면 가독성이 좋아지지 않을까. 성능은 일단 제쳐두고 가독성만을 생각하며 코드를 작성해..
[C++] 백준 1024번: 수열의 합 https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 오답 풀이 예제에 대해서 하나씩 계산을 해보았다. 우선, N에 예제 출력의 수열 길이를 나누었다. 그러자 규칙을 발견했다. 규칙은 다음과 같았다. 주어진 수를 N, 출력이 될 수열의 길이가 L이라고 했을 때, 다음 중 하나를 만족하면 답이 있다. L이 짝수이며 N에 L을 나누었을 때 나머지가 0.5이다. L이 홀수이며 N에 L을 나누었을 떄 나누어 떨어진다. 출력이 될 수열에서 첫 번째 값은 다음처럼 계산했다. L이 짝수라면 N에 L을 ..
[C++] 백준 13305번: 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 오답 풀이 도시 나열의 전체 구간[0, N - 1]에서 기름 단가가 가장 낮은 곳을 찾는다. 그곳의 위치를 K라고 하자. 그 이후 구간[K, N - 1]의 전체 도로의 길이를 구한 뒤, K 도시의 기름 단가를 곱한 값을 ans에 누적한다. 이제, 도시 나열의 남은 구간[0, K - 1]에서 기름 단가가 가장 낮은 곳을 찾는다. 그리고 위를 K가 0이 될 때까지 반복한다. 이렇게 해서..
[C++] 백준 1912번: 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 오답 풀이 먼저, 누적합 배열을 계산했다. 그리고 누적합 배열에서 최소값과 최대값을 찾았다. 최소값보다 뒤에 있는 요소 중에 최대값을 찾고, 최대값보다 앞에 있는 요소 중에 최소값을 찾았다. 그리고 그 두 경우에서의 차 중 큰 값을 답으로 출력했다. 그리고 틀렸다. 정답 풀이 https://sihyungyou.github.io/baekjoon-1912/ 백준 1912번 : 연속합 BOJ sihyungyou...
[C++] 백준 2143번: 두 배열의 합 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net Two Pointer로 어떻게 푸는거지 생각하다가 포기하고 답을 찾아봤다. 나는 아무리 생각해도 \(O({N^2M^2})\) 밖에 생각나지 않았다. https://debuglog.tistory.com/155 백준 2143번 - 두 배열의 합 백준 2143번 - 두 배열의 합 https://www.acmicpc.net/..
[C++] 백준 1644번: 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 에라토스테네스의 체와 두 포인터를 활용하여 풀 수 있는 문제다. N까지의 소수 리스트를 구하는데 시간이 상대적으로 더 오래 걸린다. 처음 제출에서 시간초과가 나서 두 번째 제출에서는 sqrt, vector::size 중복 연산을 없애고 그 외 자잘한 산술연산도 줄였더니 AC를 받을 수 있었다. #include using namespace std; #define TC(T) int T; cin >> T; while(T--) #define FAST_IO cin.tie(NULL); ios::sync_with_stdio(fa..
[C++] 백준 17404번: RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 전형적인 DP 유형의 문제다. 하지만 거기서 조금만 더 생각해야 했던 문제. 첫 번째 집을 어떤 색으로 칠했냐에 따라 마지막 집의 색이 제한된다. 그래서 나는 첫 집을 빨간색, 초록색, 파란색으로 칠했을 경우로 나누어 계산했다. 매 번 배열을 INF로 초기화 한 뒤, 앞 단계에서의 최솟값을 찾는 방식이다. #include using namespace std; #defi..
[C++] 백준 1806번: 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 골드4라기에는 난이도가 쉬운 편인 것 같다. 두 포인터라는 알고리즘 분류로 돼 있다. 나는 이름만 보고는 흔히 생각하는 start와 end를 0부터 N - 1까지 각각 훑는 O(N^2) 알고리즘인가 싶었다. 하지만 검색해서 알아보니 O(N) 알고리즘이었다. https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%E..

티스토리툴바