본문 바로가기

백준/Gold71

[BOJ] 1800 : 인터넷 설치 문제 링크 https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 1번과 N번 컴퓨터를 연결시키기 위해 필요한 비용중 최대값의 최소가 되도록하는 문제. 풀이 일단 1번과 N번 컴퓨터를 최대 효율로 연결시켜야 하므로 다익스트라 알고리즘을 사용해야하는 것을 알 수 있다. 그런데 기존 다익스트라는 비용이 계속해서 누적된다. 그리고 그 누적 비용이 가작 적게 들도록 N에 도달하는 것이 보통인데, 여기서는 비용들 중 가.. 2022. 4. 20.

[BOJ] 16639 : 괄호 추가하기 3 문제 링크 https://www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계 www.acmicpc.net 주어진 식에 괄호를 추가해서 가장 큰 값을 만들어내는 문제. 풀이 DP를 이용해서 구간별로 가장 큰 값을 계속 구한다음 마지막에 1부터 N까지 범위에서 가장 큰 값을 출력해주면 된다. 수식에 들어가는 숫자는 0~9사이의 숫자이므로 음수는 식에 입력되지 않는다. 먼저 내가 했던 실수는 "가장 큰 값" 을 출력한다는 키워드에만 집중해서 구간별로 최대값만 계속 구하고 있었다... 2022. 4. 19.

[BOJ] 17780 : 새로운 게임 문제 링크 17780번: 새로운 게임 (acmicpc.net) 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 재현이가 체스판으로 만든 새로운 게임이 종료되기까지 몇 턴이 걸리는지 출력하는 문제. 요즘 백준 문제집 중에서 danimartinwife 님이 올려주신 ★직접 코테 광탈하면서 모은 문제들☆ 이라는 문제집을 풀어보고 있는데 재밌는 문제들이 많은 것같다. 풀이 규칙을 간단하게 설명하자면 총 K개의 말이 있는데 한 턴에 1번말부터 K번말까지 순서대로 움직인다. 단, 말은 여러개 겹칠 수 있고 만약 말이 겹쳐.. 2022. 4. 15.

[BOJ] 10021 : Watering the Fields 문제 링크 https://www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net Farmer John 을 도와서 모든 field에 물을 주기위해서 필요한 최소비용을 출력하자. .. 2022. 4. 14.

[BOJ] 15684 : 사다리 조작 문제 링크 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 백트래킹으로 완전탐색하기. 풀이 기존의 사다리에 3개 이하의 새로운 다리를 놓아서 i번 사다리값이 i가 나오도록 만드는 문제. 백트래킹을 통해서 새로 다리를 놓을 위치를 정한다. 여기서 다리의 여부는 is_connected 배열을 이용해서 저장했다. is_connected[높이][막대 번호1][막대 번호2] 이렇게 3차원배열로 만들어주었고 값이 true면 1번 2번 막대 사이에 가로로.. 2022. 4. 14.

[BOJ] 14499 : 주사위 굴리기 문제 링크 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 특별한 알고리즘 없이 풀 수 있는 시뮬레이션 문제. 풀이 정말 특별한 알고리즘 없이 명령이 1(동쪽), 2(서쪽), 3(북쪽), 4(남쪽) 중에 무엇인지에 따라 주사위를 굴려주기만 하면된다. 만약 이동했을 때 범위를 벗어난다면 스킵해주면 된다. 4방향으로 굴렸을 때 각 면이 어디면으로 이동하는지만 잘 생각해보면 풀 수 있.. 2022. 4. 8.

[BOJ] 18866 : 젊은 날의 생이여 문제 링크 https://www.acmicpc.net/problem/18866 18866번: 젊은 날의 생이여 욱제의 젊은 날이 될 수 있는 최대 기간, 즉 문제의 조건을 만족할 수 있는 최대의 1 ≤ K = 0; i--) { bool chk1 = false; bool chk2 = false; if (Min_Happy_Young[i] > Max_Happy_Old[i + 1]) chk1 = true; if (Max_Unhappy_Young[i] > N; int ans = -1; for (int i = 1; i > a >> b; Happy[i] = a; Unhappy[i] = b; } int Min = INF; int Max = -1; for (int i = 1; i = 0; i--) { if (Unhapp.. 2022. 4. 8.

[BOJ] 18858 : 훈련소로 가는 날 문제 링크 https://www.acmicpc.net/problem/18858 18858번: 훈련소로 가는 날 1 이상 M 이하의 정수로 이루어진 길이 N의 수열 중 논산인 것의 개수를 998,244,353으로 나눈 나머지를 출력한다. www.acmicpc.net 논산(Non-산)인 수열이 몇 개인지 출력하는 문제. 풀이 논산이란 Non-산 즉 산이 아닌 수열을 의미한다. a1 a3 처럼 올라갔다 내려가는 형태의 수열을 산이라고 부르기로 한다. 여기서 DP배열을 어떻게 선언할지가 관건인데, 수열의 i번째 수에 대해서 3가지의 경우로 나누어서 생각할 수 있다. 1. i-1번째 수와 비교했을 때 i번째 수가 더 큰 경우. 즉, 올라온 경우(오르막) 2. i-1번째 수와 비교했을 때 i번째 수가 .. 2022. 4. 6.

[BOJ] 5582 : 공통 부분 문자열 문제 링크 5582번: 공통 부분 문자열 (acmicpc.net) 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 두 문자열이 가지고 있는 공통 문자열의 최대 길이를 출력하는 문제. 풀이 주어진 문자열을 각각 A, B 라고 하겠다. 나는 A 문자열의 문자를 돌면서 각각을 시작점으로 B 문자열과 비교하는 방식으로 탐색했다. A[0] 부터 A[length - 1] 까지 돌면서 각 문자를 시작점으로 B의 문자열과 비교했다. 모든 A의 문자마다 B문자열 첫 인덱스인 0번째부터 비교를 계속 해나가면 시간이 .. 2022. 4. 5.

이전 1 2 3 4 5 6 7 8 다음

티스토리툴바