본문 바로가기

Problem Solving

(20)

[Java] 백준 31804 - Chance! https://www.acmicpc.net/problem/31804풀이처음에는 그리디 문젠가? 했는데 그건 아니었고 dp 문제였다.찬스를 사용한 경우와 사용하지 않은 경우 둘로 나눠서 dp 배열을 채워주면 된다. i = 점수dp[i][0] = 찬스를 아직 사용하지 않았을 때dp[i][1] = 찬스를 이미 사용했을 때 dp[i][0]을 채우기 위해서는 dp[i - 1][0], dp[i / 2][0]의 값을 살펴보고dp[i][1]을 채우기 위해서는 dp[i - 1][1], dp[i / 2][1], dp[i / 10][0]의 값을 살펴본다. 주의할 점은 i가 2의 배수인지도 확인해야 한다.코드더보기import java.io.*;import java.util.*;public class Main { private..

[Java] 백준 31792 - 한빛미디어 (Hard) https://www.acmicpc.net/problem/31792문제풀이삽입/삭제/탐색 모두 시간 복잡도 O(logN)에 가능한 이진 탐색 트리를 활용할 수 있다.질의 3 (탐색) 같은 경우 그리디하게 접근할 수 있는데, 그냥 가격이 낮은 책부터 진열하다가 새로운 페이지가 필요하면 추가하면 된다. 물론 하나하나씩 탐색하면 O(N)이 되므로 S = S * 2 같은 식으로 탐색하기. (TreeMap.higerKey(Key k) 메서드를 활용하면 쉬움) 코드더보기import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = n..

[Java] 백준 2411 - 아이템 먹기 https://www.acmicpc.net/problem/2411 풀이 아이템을 체크포인트 삼아 문제를 여러 작은 행렬 경로 문제로 나누기! 예를 들어, 예제 입력 1의 경우에는 아래와 같이 구역을 나눠서 각 구역마다 행렬 경로 문제 적용 구역을 나눈다고 표현했는데 사실 아이템을 왼쪽 아래 (1, 1) 와 가까운 기준으로 정렬하고 차례대로 먹으로 가면 됨 추가로, 시작점 (1, 1)과 도착점 (N, M)에도 아이템이 있다고 생각하면 구현 때 편함 코드 더보기 import java.io.*; import java.util.*; public class Main { public static class Point { public int row, col; public Point(int r, int c) { row..

[Java] 백준 31716 - 현대모비스 자율 주행 테스팅 1 https://www.acmicpc.net/problem/31716 풀이 한 트랙에서 1열 → N열로 이동하는 최소거리는 BFS 돌리면 금방 나오는데 한 트랙에서 다음 트랙으로 넘어갈때 이동 거리를 꼼꼼하게 처리해줘야 한다. 특히, 해당 트랙 도착점의 행과 다음 트랙 시작점의 행을 맞춰주는 작업이 필요하다. 코드 더보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new S..

[Java] 백준 1707 - 이분 그래프 https://www.acmicpc.net/problem/1707 풀이 각 노드마다 1과 -1을 번갈아 매기면서 그래프 탐색 (BFS/DFS): 1이 들어가야할 노드에 이미 -1이 들어가있으면 NO -1이 들어가야할 노드에 이미 1이 들어가있으면 NO 별 문제없이 그래프 탐색이 끝나면 YES 코드 더보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int K = Integer.parseInt(br.readLin..

[Java] 백준 16724 - 피리 부는 사나이 https://www.acmicpc.net/problem/16724 풀이 단순히 구역의 개수만 출력하는 문제라 유니온 파인드 같은 알고리즘 없이도 풀이가 가능한 것 같다. 특정 칸에서 방향 따라 이동하면서 구역의 번호를 매기면 되는데 이동하다가 1. 아직 확인되지 않은 칸에 도착 ⇒ 현재 번호를 매김 2. 현재 번호가 적힌 칸에 도착 ⇒ 사이클이니까 이동 금지하고 비어있는 칸에서 새로운 구역 번호를 매기면서 이동 시작 3. 이전 번호가 적힌 칸에 도착 ⇒ 두 구역이 연결됐으니까 구역 카운트 하나 줄이고 비어있는 칸에서 새로운 번호를 매기면서 이동 시작 코드 더보기 import java.io.*; import java.util.*; public class Main { public static void ma..

[Java] 백준 7579 - 앱 https://www.acmicpc.net/problem/7579 풀이 얼핏 봐도 배낭 문제를 많이 닮아 있다 dp[i][w] = 최대 무게가 w인 배낭에서 i번째 물건까지 판단했을 때의 최대 가치 dp[i][m] = 최대 메모리가 m인 상태에서 i번째 앱까지 판단했을 때의 최대 비용 하지만 이렇게 하기에는 m이 최대 10,000,000까지 커져서 안됨 대신 기준점을 메모리가 아닌 비용으로 잡으면 dp[i][c] = 최대 비용이 c인 상태에서 i번째 앱까지 판단했을 때의 최대 메모리 사용량 여기서 c는 최대 100×100 위의 식을 이용해서 우리 원하는 메모리를 초과하는 비용의 최소를 구하면 끝! 코드 더보기 import java.io.*; import java.util.*; public class Ma..

[Java] 백준 21276 - 계보 복원가 호석 https://www.acmicpc.net/problem/21276 풀이 조상-자손 관계를 이용해서 위상 정렬 부모-자식 관계를 출력하는 건 전체 출력에서 자식의 이름이 한 번만 등장한다는 점을 이용할 수 있음. 가장 밑에서 부터 위로 올라가면서 자식들을 출력하는데 이미 나온 이름은 출력하지 않도록 하면 됨. 문자열 처리를 위해 HashMap 사용 코드 더보기 import java.io.*; import java.util.*; public class Main { public static class Person { public String name; public int indegree, outdegree; public ArrayList ancestors; public ArrayList descendants..

이전 1 2 3 다음

티스토리툴바