백준

1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 수를 묶거나(두 수의 곱) 묶지않고 주어진 수열의 합의 최댓값을 구하여라. 풀이 3가지의 경우의 수로 나눠서 최선이 무엇인지 생각해보고 풀었습니다. 양수의 경우는 큰 값끼리 묶는 것(곱하는 것)이 가장 최선 음수의 경우는 가장 작은 값끼리 묶는 것(곱하는 것)이 가장 최선 음수 중에서 남는 값이 있다면 묶는 것(곱하는 것)이 가장 최선 양수의 경우 while (positive.size() > 1 ){ int x = positive.poll(); int y..

12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 문제 문자열 S가 주어졌을 때 2가지 연산을 진행하여 주어진 T를 만족하는 문자열을 만들 수 있는지 여부를 검사하여 출력하시오. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Main { public static int answer = 0; public ..

1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 N개의 정수가 주어졌을 때, X라는 정수가 있는지 없는지 여부를 출력하시오. 풀이 정렬 A = new int[N]; for(int i=0; i t ? binarySearch(t, start, mid) : binarySearch(t, mid+1, end); } 이진 탐색을 다음과 같이 재귀로 구현하였다. 중심값을 구한다. 만약 현재 탐색할 영역이 1개 밖에 없고, 그 값이 타겟값과 다르다면 존재하지 않는 값이므..

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 양방향 간선이 주어졌을 때 가장 거리가 먼 두개의 정점을 구하세요 풀이 이 문제의 힌트는 어느 한 정점에서 다른 정점까지의 거리를 구했을 때 가장 큰 거리를 가지는 정점이 가장 거리가 먼 두개의 정점 중 하나라는 것이다. Node public static class Node{ int edge; int distance; public Node(int edge, int distance){ this.edge = edge; this.distance ..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 2차원 배열이 주어졌을 때 1이 있는 곳만 이동할 수 있다. (0, 0)에서 (N-1, M-1)까지의 최소 경로의 이동 횟수를 구하여라 ( (0,0)에서 시작할때도 횟수 1추가 ) 풀이 값을 받아준다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); N = Integer.parseInt(st.ne..

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 간선이 주어졌을 때 너비 우선 탐색과 깊이 우선 탐색의 결과 값을 구하시오. 단, 여러 정점으로 방문할 수 있다면 작은 값부터 방문하세요 풀이 먼저 값을 받아줍니다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int N =..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 A → B → C → D → E 이렇게 관계가 그려지도록 이어지는 그래프가 존재한다면 1을 출력하라는 문제이다. 이렇게 되기 위해서는 DFS를 통해서 깊이가 5가 되는 경우를 출력하면 된다. 풀이 DFS를 수행하면서 depth가 5가 된다면 DFS를 종료하고 출력하면 된다. flag를 하나 두고 depth가 5라면 flag를 true로 전환해 DFS를 종료한다. 만약 현재의 DFS가 찾지 못하고 종료된다면 현재 값은 방문하지 않은 것으로 하고 종료한다. private static void DFS(int num, int depth){ if(flag || depth ..

2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 수의 자리 N이 주어졌을 때, 1의 자리, 10의 자리, … , 10^(N-1)자리 수가 모두 소수인 값을 오름차순 정렬로 출력하시오. 풀이 해당 문제는 DFS 뿐만 아니라 소수의 특징도 알고 있다면 빠르게 풀 수 있다. 소수의 특징 1의 자리 소수는 반드시 2, 3, 5, 7 만 올 수 있다. 2 이상의 자리 소수는 반드시 1, 3, 7, 9 만 올 수 있다. 이 두 특징으로 인해 DFS가 훨씬 빠르게 진행할 수 있다. 두 가지 경우를 나눠서 ..