공부공간

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. www.acmicpc.net 정렬 후, 투포인터를 이용해 원소의 차이를구해준다. 투포인터가 가리키는 차이가 M 을넘은경우 이후의 ii값증가는 볼필요가 없다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public c..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 3X2 이차원배열과 (0번째는 최댓값계산 , 1번째는 최솟값 계산) 3X1 일차원 배열로 이전에서 올수있는 값중 최대 , 최소를 저장해놓고 다음 STEP을 진행한다. package 풀문제2; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 내려가기 { publi..

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net N번째 큰수를 구하기위해서 N^2의 배열을 선언한다 메모리제한이 12mb이므로 1500*1500*4 = 9mb를 사용하고 index의 최댓값을 저장할 일차원배열을 선언한다. N번 돌면서 일차원 배열의 최댓값을 구하고 그 인덱스를 하나 줄여준다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTo..

https://www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net NXM맵에서 직선방향으로 K만큼 이동할때에, 목적지까지 갈수있는 최단 시간을 구하는문제이다. 최단시간이고 N,M이 1000이라 BFS로 풀릴것같았다. 먼저, K만큼 1 ) 이동중 범위를 벗어나는경우 2 ) # 벽을 만나는경우 이 두가지의 경우에는 K를 break처리해주었다. import java.io.BufferedReader; import java.io.InputStreamReader..

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 상어의 움직이는 칸수 ( 최대 3칸 ) 에따라서 DFS를 구현하면 풀리는 문제이다. 매 DFS STEP마다 최댓값을 갱신하여준다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.ut..

https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문�� www.acmicpc.net 노드간 사이클을 찾는 문제였다. DFS풀이는 바로생각났지만, BFS로 궁금한점이 생겨서 테스트해봤던 문제, 사이클이 존재하면 최단거리로 도달하는 시간만 체크해주면 풀릴거같았다. 예를들어 AAAAA BBBBA AAABA ABABA AAAAA 와 같은 입력에서 어느 A에서 시작하더라도, 같은 시간으로 도달하는 한점이 생긴다 => 사이클이있다. 이 가설?같은거를 증명해보았는데 문제제약조건인..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라� www.acmicpc.net 각 데드라인이 정해져있는 문제에서 최대한 많은 컵라면을 받으며 문제를 풀었을때 받을수있는 컵라면의 개수를 구하는 문제이다. 처음 바로생각난것을 정렬+ 그리디인데, 분명 반례가 존재한다는 것을 알고 우선순위큐에 모든 노드를 넣은후 Time을 증가시키면서 Time보다 작은 라면들을 선택하면서 진행해보았다. 첫번째 시도 import java.io.BufferedReader; import java.io.Inpu..