본문 바로가기

분류 전체보기

 (386)
[boj] 백준 14888 연산자 끼워넣기 (c++) - 백트래킹 [문제] https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net [풀이] 백트래킹 문제. N개의 연산자 수를 모두 채우면 재귀를 종료하고 그 결과값을 비교하여 최댓값, 최솟값을 갱신해준다. [코드] #include #include #include #include #include #include using namespace std; int N; int operands[11]; int operator..
[boj] 백준 11052 카드 구매하기 (c++) - dp [문제] https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net [풀이] 카드팩의 가격에 따라 최댓값이 달라진다. 예를 들어 4개의 카드만큼을 구매하고자 한다면, 4개가 들어있는 카드팩, 3개가 들어있는 카드팩+1개가 들어있는 카드백, 2개가 들어있는 카드팩*2, 이런 식으로 구매가 가능하다. 즉 N개의 카드 구매에 대해 N-a개의 카드를 구매 + a개의 카드를 구매하는 가능성들을 비교하여 최대 비용을 구하면 된다. 따라서 점화식은 dp[N] = max(dp..
[boj] 백준 2179 미로탐색 (c++) - BFS [문제] https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] 기본 bfs 문제. cnt 배열에 이동 칸 수를 기록한다. [코드] #include #include #include #include #include #include using namespace std; char board[102][102]; bool visited[102][102]; int cnt[102][102] = {0, }; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0,..
[boj] 백준 1105 팔 (c++) [문제] https://www.acmicpc.net/problem/1105 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 만약 두 수의 자릿수가 다르다면 답은 무조건 0이다. 그 사이에 10, 100, 1000 등이 존재하기 때문이다. 예를 들어, 1과 13 사이에는 10이, 120과 1200 사이에는 1000이 존재한다. 두 수의 자릿수가 같다면 앞에서부터 비교해봐야 한다. 8808과 8880에 대해 답은 2가 된다. 앞의 88은 바뀌지 않기 때문이다. 따라서 앞에서부터 각 자리수의 숫자가 달라질 때까지 비교해주며 8인 경우만..
[boj] 백준 1300 k번째 수 (c++) - 이분 탐색 [문제] https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net [풀이] 문제 자체는 단순하지만 n의 크기가 너무 커 2차원 배열을 1차원 배열로 직접 옮겨서는 해결할 수가 없다. 따라서 이분 탐색을 이용해야 한다. 먼저 low는 1, high는 n*n으로 세팅한 후 mid 값보다 작거나 같은 수들의 개수를 구한다. 예를 들어, n = 4, k = 7 이면 다음과 같은 2차원 배열이 될 것이다. 1 2 3 4 2 4 6 ..
[boj] 백준 1655 가운데를 말해요 (C++) - heap [문제] https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net [풀이] 이런 접근방식은 도대체 어떻게 생각해내는건지...?! 최대힙과 최소힙을 구현하여 해결할 수 있다. 값을 넣을 때 다음 두가지 조건을 만족해야한다. 1. 최대힙의 크기는 최소힙의 크기와 같거나 '1'만큼 더 커야한다. 2. 최대힙의 top은 최소힙의 top과 같거나 더 작아야 한다. 최대힙의 top값이 순서대로 입력될 때의 중간값이 된다. 1, 5, 2, 10, -..
[boj] 백준 9465 스티커 (c++) - dp [문제] https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net [풀이] 처음 bfs 문제인 줄 알고 엄청 헤맸다.....n ≤ 100,000 이라 dp로 해결할 수 있다. 첫번째 스티커를 뗀다고 생각해보자. 그 다음에 뗄 수 있는 스티커는 오른쪽과 아래의 10, 30을 제외한 스티커이다. 50을 뗀다면 그 다음은 100, 10, 60 처럼 위, 아래로 움직이며 스티커를 뗄 수 있을 것이다. 그렇다면 50만 뗄 수 있을까? 아니다! 50이 ..
[boj] 백준 11505 구간 곱 구하기 (c++) - 세그먼트 트리 [문제] https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net [풀이] 세그먼트 트리를 이용한 standard 문제이다. 구간 합을 구간 곱으로만 바꿔주면 되는데 sum의 경우(start > right || end < left) 조건에서 0을 return하지만 곱의 경우 0이 반환되면 값이 전부 0이 되므로 1을 return하도록 한다. [코드] #include #include #incl..

티스토리툴바