PS/백준

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { /** * 그리디 * 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. * 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) * 가장 시간이 적게 사람들을 줄을 세우는 방법 * 입력 예) * 5 * 3 1 4 3 2 * 출력 예) * 32 */ public static void main(String[] args) throws IOExcep..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { /** * 주유소 * 주유소 마다 리터강 가격이 주어지며 주유소 사이에 거리가 주어진다. * 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. * 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. * 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. * 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1..

플레5 문제인 오아시스 재결합 문제이다. 스택을 사용하여 문제를 풀었다. 겁도 없이 플레5 문제를 풀게 되었는데 스택을 사용한다는 것을 알고 있으니 생각보다는 괜찮았던 것 같다. (몇 시간 걸리긴 했지만) 확실히 Java 보다는 Python이 좀 더 간편한 것 같다. 자바로 푼 건 파이썬으로, 파이썬으로 푼건 자바로 풀어봐야겠다. # 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. # 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램 import sys # 입력 N(1

백준의 두 배열의 합 문제를 풀어보았다.(Java) 구현에 사용한 알고리즘은 TwoPointer이다. TwoPointer에 대해 생소하여서 기존에 풀었던 기초라고 생각한 문제로 다시 풀어보았다. 이번 문제로 개념을 좀 잡은 것 같다. 작성한 코드는 아래와 같다. 두 배열의 부분합을 계산한 뒤 리스트에 넣고 정렬한다. 정렬한 리스트를 토대로 투 포인터를 사용하여 제시한 합과 동일한 부분합을 계산한다. package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; impo..

백준의 색종이 붙이기 문제를 풀어보았다.(Java) 구현에 사용한 알고리즘은 Backtracking이다. 백트래킹 문제로 1x1, 2x2, 3x3, 4x4, 5x5로 이루어진 색종이 5개를 이용하여 1이 적힌 모든 칸을 색종이로 덮는 문제이다. BOJ1987 문제의 심화 버전인 것 같다. 5x5부터 비교하여 최대한 색종이를 적게 사용하도록 한다. 보드의 마지막에 도착하면 가장 작은 값을 초기화 한다. 작성한 코드는 아래와 같다. package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BOJ17136 { static int[][] grid =..

백준의 달빛 여우 문제를 풀어보았다.(Java) 친구의 소개로 풀어본 문제인데 오랜만에 PS를 풀어 관련 개념공부도 같이하였다. 구현에 사용한 알고리즘 또는 자료구조로는 Dijkstra, Graph, 우선순위 큐를 사용했다. 맨 처음에는 Java에서 보통 입력 속도를 줄이기 위해 사용하는 BufferedReader와 그냥 받은 입력을 String 배열에 담는 작업을 했는데 시간초과가 발생했다. 그래서, StringTokenizer를 사용했더니 통과했다. 작성한 코드는 아래와 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; // 달빛 여우, 달빛 ..