본문 바로가기
728x90

전체 글129

[JAVA]백준 2357번: 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 1. 문제 설명 N개의 정수들이 주어지고 a,b 쌍이 M개 주어질때 a번째부터 b번째까지 정수의 최소, 최댓값 출력 2. 풀이 간단한 인덱스(세그먼트)트리 문제이다. 부분합 대신 최댓값, 최솟값만 저장해서 update, query를 진행하면 된다. *로직 - 정수를 입력 받는다. - 입력받은 정수로 minTree(최솟값 저장), maxTree(최댓값 저장)를 .. 2021. 8. 2.
[JAVA]백준 1102번: 발전소 https://www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 1. 문제 설명 고장 나 있지 않은 발전소를 이용해서 고장 난 발전기를 가동할 수 있다. 적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오. 2. 풀이 dp와 비트마스킹을 이용해서 풀 수 있다. 현재 켜져있는 발전소 상태를 bit로 표현한다면 아래와 같이 dp로 구현할 수 있다. 현재 꺼져 있는 발전소 X가 있다면 현재 켜져 있는 발전소들 중 X를 키는 .. 2021. 7. 29.
[JAVA]백준 2094번: 강수량 https://www.acmicpc.net/problem/2094 2094번: 강수량 첫째 줄에 정수 n(1 ≤ n ≤ 50,000)이 주어진다. 다음 n개의 줄에는 두 정수 y(0 ≤ |y| ≤ 1,000,000,000), r(1 ≤ r ≤ 1,000,000,000)이 주어지는데, 이는 y년도의 강수량이 r이라는 의미이다. 이러한 정보는 y www.acmicpc.net 1. 문제 설명 X 년도에는 Y 년도 이후 가장 많은 비가 내렸다 라고 말하려면 3가지 조건이 만족해야 한다. 1. Y 년도, X 년도, 그리고 그 사이의 모든 년도들의 강수량에 대한 정보가 알려져 있다. 2. X년도의 강수량은 Y 년도의 강수량 이하이다. 3. Y < Z < X를 만족하는 모든 Z에 대해서, Z 년도의 강수량은 X 년도.. 2021. 7. 28.
[JAVA]백준 1072번: 게임 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 1. 문제 설명 현재까지의 게임 횟수 X, 이긴 게임 Y이 주어진다. 지금부터 형택이는 게임을 하면 무조건 이긴다고 할 때 게임을 최소 몇 판을 해야 승률이 변하는지 구하는 문제. 2. 풀이 2가지로 풀이가 가능하다. 두 방법 모두 Z가 100, 99 일 때는 -1을 출력하고 98 이하일 때부터 계산을 수행한다. 99,100일 때 -1을 출력하는 이유는 99,100일 때는 아무리 게임을 더.. 2021. 7. 23.
728x90

티스토리툴바