본문 바로가기

Algorithm64

[백준 Silver 1] 11048 이동하기 - Java 문제링크 : https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 접근 과정 : 해당 문제는 DP를 이용해서 풀수 있다. DP[r][c] = maze[r][c] + Math.max(dp[r-1][c], Math.max(dp[r][c-1], dp[r-1][c-1])) 이다. Top-down 과 Bottom-up으로 풀어보았다. 소스 코드 및 결과 : package BOJ; /* 이동하기 Top-down */ import java.io.*.. 2022. 1. 7.
[백준 Silver 3] 10825 국영수 - Java 문제링크 : https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 접근 과정 : 정렬을 위한 비교 메소드를 사용할 수 있는지 묻는 문제인것 같다. 국어, 영어, 수학, 이름 순으로 비교를 해야하고 점수는 숫자이지만 이름은 문자이다. 한번에 비교하고자, score 클래스를 만들어서 사용했다. 조건에 맞게 비교 우위를 설정하고 우선순위 큐에 집어넣어서 출력했다. 소스 코드 및 결과 : package BOJ; /* 국영수 */ imp.. 2022. 1. 7.
[백준 Silver 3] 3085 사탕 게임 - Java 문제링크 : https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 접근 과정 : 초기 상태에서 가장 많이 사탕을 먹을 수 있는 경우를 계산 사탕을 바꿀 수 있는 경우들을 탐색하며, 바꿨을 때 먹을 수 있는 사탕의 개수를 계산 사탕의 개수를 계산할 때마다, 최대값을 갱신하여 리턴. + 사탕의 실제 값은 바꾸지 않고 좌표로만 확인한다. 소스 코드 및 결과 : package BOJ; /* 사탕 게임 */ import java.io.*; public class BOJ3085 { public static void main(String[] args) throws NumberFo.. 2022. 1. 7.
[백준 Gold 1] 2213 트리의 독립집합 - Java 문제링크 : https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 접근 과정 : 이전에 풀었던, '트리에서의 다이나믹 프로그래밍' 접근을 통해서 문제를 해결하려고 했다. 추가적으로 고민했던 부분은 독립 집합의 원소들을 추적하는 부분이었다. 결국 현재 정점의 독립 집합 포함 여부에 따라서 연결된 다음 정점의 포함여부가 결정되기에, 이 부분을 고려해서 작성했다. DP[][] : i번 정점의 독립집합 포함 여부 , [n+1.. 2022. 1. 6.

티스토리툴바