본문 바로가기

boj127

[Java] BOJ 9084번 동전 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 문제에서 주어진 수는 너무 큰 관계로 3개의 동전 2원, 3원, 5원으로 10원을 만드는 경우를 구해보겠습니다. 1 2 3 4 5 6 7 8 9 10 2원 0 1 0 1 0 1 0 1 0 1 2원의 경우 위와 같은데 이때, 총경우의 수를 구해야 하므로 구한 결괏값을 그대로 유지하고 새로 갱신을 해나가야 합니다. 다음으로 3원의 경우를 보겠습니다. 예를 들어, 3원의 경우 앞서 2원으로 만들 수 있는 경우의 수들.. 2021. 7. 16.
[Java] BOJ 13023번 ABCDE 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 DFS를 사용하여 해결했습니다. 문제를 이해하지 못해서 어려웠던 문제였습니다. 간단하게 설명하자면 DFS를 사용하여 문제에서 요구하는 ABCED 즉, 5개의 노드를 한 번에 탐색이 가능하다면 1을 출력하면 되는 문제였습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public clas.. 2021. 7. 15.
[Java] BOJ 17472번 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 BFS와 Prim 알고리즘을 사용하여 해결했습니다. 자세한 내용은 코드의 주석을 참고해주세요. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.St.. 2021. 7. 15.
[Java] BOJ 5582번 공통 부분 문자열 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 문제에서 나온 1번 예시를 풀어보면 ABRACA~ 를 S1이라 하고 인덱스는 i, ECADA~ 를 S2라 하고 인덱스는 j라고 한다면 S1[i] == S2[j]라면 이전까지 연속되는 부분 문자열에 새로 공통된 문자가 들어가므로 S1과 S2에 공통되는 이전 문자인 memo[i -1][j - 1]에 저장된 길이에 + 1을 하여 즉, memo[i -1][j - 1] + 1을 현재 위치에서 공통되는 연속된 부분 문자열인 m.. 2021. 7. 13.
[Java] BOJ 6593번 상범 빌딩 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 BFS를 이용하여 해결했습니다. 이때, 제 코드에서 Info 클래스의 생성자의 순서는 x, y, z이고 축의 사용은 building[z][y][x] 즉, z는 층, y는 행, x는 열로 사용했어서 주의해야 합니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.uti.. 2021. 7. 12.
[Java] BOJ 2668번 숫자고르기 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 DFS를 사용하여 해결했습니다. 문제를 잘못이해하여 생각보다 어렵게 해결했던 문제입니다. 문제에서 요구하는 것은 표가 주어졌을때, 표를 배열 arr이라고 생각하고 arr의 모든 인덱스 idx를 DFS의 시작점으로 탐색합니다. 만약 arr[idx] 가 찾고자하는 idx와 같다면 이는 문제에서 요구하는 조건에 맞아 떨어지므로 list에 추가하면 되고 다르다면 arr[idx]로 DFS를 수행하면 됩니다. 자세한 사항은 코드의 주석을 참고해주세요. 코.. 2021. 7. 9.

티스토리툴바