본문 바로가기

백준35

[Gold IV] 알고스팟 - 1261 (Java) 문제 요약 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1 크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)이다. 단, 미로의 밖으로 이동할 수는 없다. 벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일.. 2023. 8. 19.
[Gold V] 빗물 - 14719 (Java) 문제 요약 2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까? 문제 분석 왼쪽과 오른쪽에서 각각 반대편으로 이동하며, 현재 위치기준으로 시작점부터 현지점까지 가장 높은값을 저장하는 배열 생성 및 저장 그후 순차탐색하며 위 두배열의 현재위치의 값 중 min값을 전체 더해 결과 출력. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int H, W; publi.. 2023. 8. 8.
[Silver I] 전쟁 - 전투 - 1303 (JAVA) 문제 요약 전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다. N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다. 문제 분석 맵을 받아서 순차적으로 탐색하며 BFS를 돌린다. 이때 찾은 병사들의 색을 기준으로 값을 갱신해준다. 코드 import java.io.BufferedReader; import java.io.IOException.. 2023. 8. 8.
[Gold IV] 여행 가자 - 1976 (Java) 문제 요약 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다. 문제 분석 도시 간의 연.. 2023. 7. 28.
[Gold III] LCS 3 - 1958 (Java) 문제 요약 문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다. 이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라. 문제 분석 기존에 풀었던 LCS2문제의 연장선에서 3차원 배열을 사용한 문제 해결. https://cornsilk-tea.tistory.com/64 [Gold IV] LCS 2 - 9252 (Java) 문제 요약 LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수.. 2023. 7. 28.
[Gold IV] LCS 2 - 9252 (Java) 문제 요약 LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 문제 분석 두 문자열 A와 B의 모든 위치를 검사하면서, 만약 두 문자가 같다면 이전 위치의 LCS 길이에 1을 더하고, 그렇지 않다면 이전 위치에서의 LCS 길이 중 큰 값을 저장한다. 이 과정을 통해 얻은 2차원 배열 dp의 마지막 요소 dp[A.length][B.length]가 두 문자열의 LCS 길이가 된다. LCS를 출력하기 위해, 문자열 A와 B의 마지막 위치에서 시작해 첫 위치까지 역순으로 이동하면서, 두 문자가 같을 경우 해당 문자를 스택에.. 2023. 7. 28.

티스토리툴바