0과 1의 쉼터

문제https://www.acmicpc.net/problem/10886 풀이홀수인 N개의 수를 입력받아 전체 합이 N의 절반을 넘는지 확인하는 문제다.import java.io.*;public class Main { public static void main(String[] args) throws IOException { // Init BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Input final int N = Integer.parseInt(br.readLine()); int cnt = 0; // Solve for (..

문제https://www.acmicpc.net/problem/6118  풀이양방향 그래프의 1번 정점으로부터의 최대 깊이를 가지는 정점의 번호와 깊이, 동일한 최대 깊이를 가지는 정점의 수를 구하는 문제다.양방향 그래프부터 구성하자.import java.io.*;import java.util.*;public class Main { static List> graph = new ArrayList(); static int N; static int[] depth; public static void main(String[] args) throws IOException { // Init BufferedReader br = new BufferedReader(new Inp..

문제https://www.acmicpc.net/problem/1325  풀이단방향 그래프가 주어질 때, 가장 많은 정점을 방문할 수 있는 시작 정점을 찾는 문제다.A가 B를 신뢰할 때 B가 해킹 당하면 A도 해킹 당한다. 신뢰 관계에 대한 단방향 그래프를 구성하자.import java.io.*;import java.util.*;public class Main { static List> graph = new ArrayList(); static int N; static int[] cnt public static void main(String[] args) throws IOException { // Init BufferedReader br = new Buffere..

문제https://www.acmicpc.net/problem/1477 풀이구간 1 ~ (L - 1)에 N개의 휴게소가 위치 A[i]에 존재하고, M개의 휴게소를 추가로 지었을 때, 휴게소가 없는 구간의 길이의 최댓값이 최소가 되도록 해야 한다.문제의 설명에서 알 수 있듯.M개의 휴게소를 전부 설치 가능한 경우에 대해휴게소가 없는 구간의 길이의 최댓값이 최소가 되어야 한다.휴게소가 없는 구간의 길이를 탐색 범위로 잡고, 이분 탐색을 하면 된다.배열 A의 앞 뒤에 경계 값을 붙여주어 계산을 쉽게 해보자.import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException..

문제https://www.acmicpc.net/problem/14921 풀이N개의 수 중 두 수의 합을 0에 최대한 가깝게 만드는 문제다.우선, A를 오름차순으로 정렬해 문제를 단순화하자.import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { // Init BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Input final int N = Integer.parseInt(br.readLine()); i..

문제https://www.acmicpc.net/problem/2565풀이유명한 LIS 문제다.우선, 전깃줄의 위치 정보를 A 또는 B를 기준으로 정렬하자.A를 기준으로 정렬해보겠다.A에서 B로 가는 전깃줄이 교차하지 않도록 최소한의 전깃줄만 제거해야 한다.교차하지 않는 전깃줄들이 최대가 되기 위해서는 A에서 B로 향하는 전깃줄들이 최대한 촘촘히 위치가 증가해야 한다.즉 B의 LIS가 교차하지 않는 전깃줄의 수와 동일하다.문제에서 요구하는 정답은 제거해야 하는 전깃줄의 수 이므로 N에서 B의 LIS를 뺀 값을 출력하자.소스코드보기

문제https://www.acmicpc.net/problem/11000풀이강의실을 최소로 사용해서 모든 강의를 끝내야 한다.강의가 끝나는 대로 다음 강의를 바로 진행할 수 있지만, 강의가 끝나지 않았는데 시작하는 강의가 있다면 강의실이 필요하다.priority queue를 사용해 쉽게 해결할 수 있다.우선, 시작 시간을 기준으로 정렬해주자.다음으로 강의 종료시간을 우선순위 큐에 넣어준다.만약 다음 강의의 시작시간이 가장 빨리 끝나는 강의의 종료시간 이후라면, 가장 빨리 끝나는 강의를 우선순위 큐에서 제거해주면 된다.그렇지 않는 경우라면 계속 우선순위 큐에 넣어주고 마지막에 전체 크기를 출력해주자.소스코드보기

문제https://school.programmers.co.kr/learn/courses/30/lessons/42898풀이MN크기의 보드에 장애물이 주어지고, (1, 1)에서 (M, N)까지 가는 최단 경로의 수를 1e9 + 7로 나눈 나머지를 출력하는 문제다.보통 좌표가 NM으로 주어지지만 여기서는 MN이다. puddles가 가지는 좌표또한 MN임을 유의하자.puddles에는 BLOCK표시를 해주자.( 0, 1 ) 또는 ( 1, 0 )에 1을 기입해 (1, 1)이 1을 가질 수 있도록 해주자.dp[i][j] : ( i, j )까지 오는 최단 경로의 수이후에는 모든 경로를 탐색하며 장애물이 없는 칸이라면 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]을 통해 최단 경로의 수를 합쳐주자..

문제https://www.acmicpc.net/problem/10395풀이두 배열을 입력받아 서로 반대되는지 확인하는 문제다.기본 값을 Y로 해주고 선형 탐색하며 같은 경우가 있다면 N으로 변경 후 결과를 출력하자.소스코드보기

문제https://www.acmicpc.net/problem/6243풀이주어진 비행 정보에 따라 지급해야 하는 마일리지를 계산하는 문제다.TC의 수는 정해지지 않으며, 0을 입력받으면 각 케이스의 종료를 의미한다. 누적 마일리지를 출력하면 된다.#을 입력하면 프로그램을 종료해야 한다.입력받은 클래스 코드가 F라면 운행 거리의 2배를, B라면 1.5배를 더해주면 된다.이코노미라면 500또는 운행 거리 중 큰 값을 더하면 된다.소스코드보기