본문 바로가기

알고리즘/백준

 (51)
[백준] 2169 로봇 조종하기[JAVA] 문제링크 : www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 로봇은 왼쪽, 오른쪽 ,아래쪽으로만 움직일 수 있다. N,M까지 이동하는데 가치의 합이 최대가 되는 경우의 그 가치의 합을 출력하는 문제다. 가치는 음수가 될 수 있는 것에 유의한다. 모든 경로를 탐색하며 가치의 합이 최대인 경우를 저장하는 방식을 쉽게 생각해볼 수 있다. 1,1에서 N,M까지의 가치의 최대합은 1,1에서 특정 지점까지의 가치의 최대합 + 그 특정 지점에서 N,M까지의 가치..
[백준] 14267 회사 문화1 문제링크 : www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 1번인 사장을 제외하고 모든 사원은 직속 상사를 1명을 가지기 때문에 회사 구조를 트리 형태라고 할 수 있다. 칭찬은 해당직원을 상사로 갖는 모든 부하로 계속 전파하기 때문에 연결된 모든 하위 트리를 탐색하면 된다. 그것을 구현하기 위해 dfs를 사용하였다. 처음에, M번 쿼리가 발생할 때마다 dfs를 수행하는 비효율적인 방법으로 코드를 짰었다. 이는 단순히, 쿼리에 대해 직원의 cost를 미리 ..
[백준] 1976 여행가자 문제링크 : www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행지가 연결되었는 지만 알면 되기 때문에 disjoint set으로 해결 가능하다. import java.io.*; import java.util.*; public class Main { public static int N,M; public static int [][]adj; public static int par[]; public static void init() { for(int i=1;i
[백준] 1963 소수 경로 문제링크 : www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 4자리 수 이므로 모든 경우의 수를 탐색하면 되는 문제이다. 어떤 4자리 수에서 숫자 하나를 바꾸어 다른 숫자로 만드는 경우는 4*9이고 이 중에서 소수일 경우만 다음 숫자가 가능하다. 이를 bfs로 구현하면 숫자를 변경한 횟수를 쉽게 알 수 있어서 bfs로 구현 했으며, 소수를 미리 isPrime에 체크했다. import java.io.*; import java.util.*; public class Mai..
[백준] 1744 수 묶기 문제링크: www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 부호가 같고, 절댓값이 큰 수끼리 묶는 것이 결과값이 큰 것이라는 것은 쉽게 알 수 있다. 숫자 1은 어떤 수와 묶는 것보다 안묶는 것이 1 더 크다는 것과 음수가 홀수일 때, 0이 있으면 0과 곱하는 것이 결과값을 더 크게할 수 있다는 것에 유의하며 코드를 짜면 된다 import java.io.*; import java.util.*; public class Main { public static v..
[백준] 14226 이모티콘 [JAVA] 문제링크 : www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 3가지 연산에 대해서 비용이 모두 1이다. S가 1000이하여서 BFS로 해결 되었다. import java.io.*; import java.util.*; public class Main { public static boolean visited[][]; public static class Node{ int emoticon; int copyCnt; public Node(){} public Node(in..
[백준] 같이 눈사람 만들래? [JAVA] 문제링크 : www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 눈사람을 2개 만들기위해 눈덩이 600개 중에 서로다른 4개를 고르는 연산을 할 경우 시간초과가 난다. 방법은, 눈덩이 N(최대 600)개로 만들 수 있는 눈사람을 배열에 저장한다 600C2 => 600*599/2 저장할 때 어떤 눈덩이를 썼는지 같이 저장한다.(나의 경우 SnowMan 클래스의 first, second) 눈사람 크기를 기준으로 정렬한다. 엘자가 600..
[백준] 11000 강의실 배정 [JAVA] 문제링크 : www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si 이분탐색 등을 생각할..

티스토리툴바