6-6화이탱

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net DFS를 사용해서 맨 첫 여행지부터 시작해서 방문가능한 곳들에 대한 확인을 한다! 여행계획대로 포문을 돌려서 방문 가능한지 본다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokeni..

https://www.acmicpc.net/problem/24337 24337번: 가희와 탑 일직선으로 다양한 높이의 건물들이 N개 존재합니다. 가희는 건물들의 왼쪽에, 단비는 건물들의 오른쪽에 있습니다. 일직선 상에 가희와 단비, 건물들은 아래와 같은 순서로 배치되어 있습니다. www.acmicpc.net 구현 문제로, 풀이법을 생각해내기 꽤 어려운 문제였다... 1. 건물의 최고 높이는 a와 b중 큰 값이다. 2. 디큐를 생성하여 a-1만큼의 오름 차순 + 최고 높이 건물 + b-1만큼의 내림차순으로 먼저 add 한다! 3. 다 add 한 후에 디큐 사이즈가 n보다 크다면, 건물 정보가 나올 수 없는 것이기에 -1을 출력한다!! 4. 여기까지 진행하면 아래와 같은 경우가 발생된다. 입력 9 1 5 -..

https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 구현문제로, 해결법을 생각해내기가 조금 어려웠다.. ArrayList iint배열을 만들어서 넣는 방식으로도 도전해봤는데 시간초과가 발생하였다.. 결국 int배열로, 입력 받을때마다 빈자리는 양보하면서 자리 배치를 하였다. 왼쪽에 2명 있다는 입력을 받으면, -> 1번째 자리가 비어있다면 한명에게 자리 양보하니까 왼쪽 (현재 왼쪽 인원수 2) -1 2번째 자리도 비어있다면 또 양보하니까 (..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 최소시간으로 bfs를 사용하여 문제를 풀었다. 1. 좌표와 시간을 가진 객체 생성 2. 큐 생성하여 시작 좌표 add 3. 0~100000 범위에서 +1, -1, *2한 좌표를 가진 객체를 큐에 add 4. k에 도달하였을때, 시간을 확인하여 최솟값 여부 확인 ! import java.io.BufferedReader; import java.io.IOExceptio..

https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 알파벳별로 개수를 저장한 다음, k개 미만인 경우에는 확인하지 않도록 한다! 그리고 k가 1일 경우의 예외처리를 해줘야 한다는 점을 주의!! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; p..

https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 1. 지름길 객체를 만들고 1) 시작 위치 오름차순 2) 끝나는 위치 오름차순 3) 거리 오름차순 으로 정렬할 수 있도록 한다. 2.ArrayList에 객체를 넣고 정렬 시킨다. 3. int배열 dp를 만들고 열의 값으로 초기화한다. 4. 지름길 갯수 만큼 포문을 돌려서 dp[시작위치]+거리를 더한 값이 기존의 dp[끝위치]보다 작을 경우, 전체 고속도로의 거리까지 포문을 돌려서 dp값..

https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net map을 이용하여 메모장의 키워드들을 넣어준다. count 변수는 처음에 n으로 세팅하고, 글을 쓰면서 사용하게 되는 키워드의 개수를 뺀다! import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Buffere..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net bfs로 해결 가능한 문제였다. 최단거리 배열 dp 현재 위치에서 출발하는 큐를 생성하여 문제를 푼다. 큐를 꺼내면서 동서남북을 확인하여 방문 여부를 본 후, 현재 거리값의 +1을 한 값을 dp에 넣는다! 방문 여부가 없는데 땅인 곳은 갈 수 없는 땅이기에 -1을 출력한다. import java.io.BufferedReader; import java.i..

https://www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 간단하게 배열을 생성하여 이미 먹은 햄버거인지 확인한다. 아주 간단한 실버3 문제였다..! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static boolean[] eatChec..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 아래의 우선순위로 정렬하고 1) 데드라인이 작은 것 2) 컵라면 수가 큰 것 풀 수 있는 문제의 컵라면 수를 넣어줄 우선순위큐를 생성한다. 포문을 돌려서 큐의 사이즈는 즉, 풀 수 있는 문제 수와 같기에 이를 문제의 데드라인과 비교하여 큐의 사이즈보다 문제의 데드라인이 더 크다면 풀 수 있기에 큐에 넣고, 큐의 사이즈와 문제의 데드라인이 같다면 큐의 가장 작은 값을 peek하여 현재 문제의 컵라면 수와 비..