골드 5인데도 하루를 꼬박 썼다. 직전에 유사한 문제 (BOJ 14502 연구소 - https://www.acmicpc.net/problem/14502)를 풀어서 조합을 이용한 풀이를 빨리 떠올렸고, 하다못해 구글링해서 아주 유사한 코드를 발견했음에도 어디가 문제인지 몰라서 한참을 헤맨 문제. (난 알고리즘 팔생각도 없고 코테합만 안정적으로 할 딱 그정도 수준만 되고싶을 뿐인데 참 어렵다.) 문제 정리 간단하게 정리하면, "NxN 크기의 도시에 집들과 치킨집들이 있다. 이 치킨집들의 숫자를 M개까지 줄일 때, '치킨 거리'의 합의 최소값을 구하시오. (치킨 거리란, 임의의 집에서 치킨집까지 거리의 최소값을 의미한다.)"로 정리할 수 있다. 풀이 처음에는 NxN의 인접 행렬로 도시를 표현하고 나서, 처음 ..
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이시간 모두 합치면 6~7시간도 넘게 걸린 문제다.ㅜ 풀이과정을 떠올리는데에는 그렇게까지 많은 시간이 걸리지는 않았지만 탐색 문제를 풀때마다 막상 세부 구현에서 문제가 생겨서 정리해놓기 위해 쓴다. 1. 문제 파악 항상 그렇지만 문제가 길수록 문제의 조건을 읽기X 이해O한 후에 본격적으로 코드를 작성하자. 이 문제를 읽고 정리할 점은 다음과 같다. - 상어는 자신의 크기보다 작은 크기의 ..
예전에 풀었던, dp 메모이제이션을 이용하는 bfs/dfs문제인 ACM craft(https://eckrin.tistory.com/entry/BOJ-1005-ACM-Craft?category=985109)들과 유사한 문제다. 이런 유형의 문제를 한두번 푸는것이 아닌데도 계속 헷갈리는 이유는, dp를 사용했다고 해서 메모이제이션을 사용하는 것이 아니라는 사실을 자꾸 망각해서 그렇다. 뭔 소리나면, Queue queue = new LinkedList(); queue.add(new Location(0,0)); while(!queue.isEmpty()) { Location removeLoc = queue.remove(); int x = removeLoc.x; int y = removeLoc.y; int valu..
1. 처음 문제를 보니깐 dp로 풀면 될 것 같아서 먼저 dp로 풀어보았다. import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input = br.readLine().split(" "); int N = Integer.parseInt(input[0]); int K = Integer.parseInt(input[1]); int[] arr = new int[100001]; //0~100000 for(int i=0; i=0; i--) arr[i..
뱀 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 49416 20232 13459 39.229% 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지..
문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예nvertexr..
문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다...
문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 입력 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. ..
문제를 보고 상하좌우 4방향을 검사하여 방문한 적이 없는 집이 하나도 없으면 새로 방문하는 단지로 풀면 되겠다 생각헸는데, 탐색 순서를 보면 문제 예제의 2번같은 경우 다른 쪽 끝을 먼저 탐색할 경우 단지의 개수를 증가시키는 연산을 하게되어 단지수를 정확하게 계산할 수 없게 되어 문제가 생긴다. 당연하게도 단지 내 집의 개수도 계산할 수 없다. 무엇보다도 이런 좌표탐색 문제의 경우 한 부분을 완료하고 다음 부분으로 넘어가야지 위와 같은 문제가 발생하지 않는다. dfs가 떠오르지 않은 것은 아니지만 dfs는 사용하기 망설여지는게 input이 과하게 클경우 시간초과가 너무 많이나서 꺼려지게됨. > DFS의 시간복잡도는 리스트의경우 O(|V|+|E|), 인접행렬의 경우 O(V^2)이므로 행렬의 최대크기가 25..
문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자. 이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해..
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 접근 (처음에는 답이 정해진 스도쿠의 경우만 생각해서 1. 행을 검사하여 1개의 0이 존재한다면 정해진 숫자 삽입 2. 열을 검사하여 1개의 0이 존재한다면 정해진 숫자 삽입 3. 3x3크기의 행렬을 검사하여 1개의 0이 존재한다면 정해진 숫자 삽입 과 같이 반복문을 이용하여 삽입하는 코드를 짜고, 왜 이게 백트래킹 문제인지 의아했지만) 출력조건에서 나와있듯이 '스도쿠 판을 채우는 방법이 여..
문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 ..