live the life you love

www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보� www.acmicpc.net 그렇게 어려운 문제는 아니었는데 복잡하게 생각을 해서 그런가 헤매다가 다른 블로그의 글을 보고 푼 문제다. 문제는 단순하다. 각 크레인 마다 1개의 박스를 옮길 수 있고 무게 제한이 있다. 한 번 옮길 때 마다 크레인이 옮길 수 있는 최대 무게의 상자를 옮겨주면 된다. 문제 해결 가장 무거운 박스와 가장 무거운 무게를 들 수 있는 크레인을 비교한다. 박스 값이 크레인 보다 크면 절대로 옮길 수..

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 숨바꼭질 3의 경우는 1,2번 문제와 달리 순간이동을 하는데 걸리는 시간이 0초다. 이것을 잘 해결 하는 것이 매우 중요하다. 이 문제는 우선순위 큐(priority queue)를 활용하는 방법과 기본적인 큐를 활용해서 푸는 방법이 있다. 순간이동을 하는데 걸리는 시간이 0초이므로, 0초에 순간이동 하는 것을 큐에 먼저 삽입을 해줘야 한다. 우선순위 큐는 최대힙으로 구성되..

www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net 숨바꼭질2는 1과 달리, 최단 시간으로 동생을 찾는 경우의 수까지 출력하는 문제이다. 경우의 수를 따로 체크하는 것을 제외하면 숨바꼭질 1 의 풀이와 똑같다. 문제해결 동생을 찾은 시간의 값을 저장하는 배열(answer)을 만든다. 최대로 걸리는 시간은 수빈이가 0에 있고, 동생이 100000에 위치하고 있을 때 1칸 씩 앞으로 가면 100000초가 걸리는 것이므로 배열..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 숨바꼭질 시리즈를 전부 풀어보려고 한다. 총 6개의 숨바꼭질 문제가 있으며, 내용은 거의 똑같지만 문제가 요구하는 조건이 조금씩 다르다. 대부분 탐색문제이며 BFS, DFS, 다익스트라를 잘 활용해서 풀면 될 듯 하다. 동생의 위치를 찾을 수 있는 가장 빠른 시간을 구하는 것이므로 BFS를 활용해서 풀 수 있다. 기본적인 BFS를 구현하면 되는 간단한 문제였다. 문제 해결 큐에 ..

www.acmicpc.net/problem/16113 16113번: 시그널 zxcvber는 외계인을 연구하는 과학자다. 그는 지난 10년간 우주에서 오는 시그널를 연구했지만, 아무런 성과가 없었다. 그러던 어느 날, 갑자기 우주에서 이상한 시그널이 오기 시작했다. zxcvber는 � www.acmicpc.net 시뮬레이션 문제였다. 구현 방법을 떠올리는데 크게 어렵진 않았지만, 사소한 오류를 고치는 과정이 꽤 걸렸다. 또한, 코드도 깔끔하지 않다. 중복된 코드도 있고 예외처리를 위해 goto를 사용했다.. 좀 더 깔끔하게 짤 방법이 있을 것이다. 문제 해결 방법 디지털 숫자를 위에서 아래로 읽었을 때 나오는 값을 '#'과 '.' 의 형태의 문자열로 따로 저장해둔다. 예를들어 2라는 숫자를 왼쪽 위에서 시..

www.acmicpc.net/problem/17479 17479번: 정식당 일반메뉴는 noodle 2개로 20,000원, 특별메뉴는 cutlet 2개와 friedrice 1개로 32,000원, 둘이 합쳐 52,000원으로 서비스메뉴 하나를 주문할 수 있다. www.acmicpc.net 해시 자료구조를 사용하고 싶어서 풀어본 문제 해시 맵을 4개 사용해서 각 메뉴, 가격, 주문수량에 맞게 정보를 저장해주면 된다. 구조체를 사용하여 해시 맵에 저장하면 더 간단하게 풀 수 있는데, 연산자 오버라이딩도 해줘야 해서 그냥 여러개의 해시맵을 만들었다. 4번 시도만에 해결했는데 틀린원인은 2개였다 service 오타 자료형 범위 오타는 금방 찾았지만, 자료형 범위를 찾는데 좀 오래걸렸다. 각 메뉴등급별로 최대 5만개..

문제링크 : https://www.acmicpc.net/problem/10836 일반적인 시뮬레이션으로 풀었더니 시간초과가 났다. 입력의 최댓값이 100만이어서 그랬다. 문제 해결 조건 1번의 애벌레의 크기에 따라 나머지 애벌레의 크기가 바뀌는 것 조건 1번의 애벌레를 먼저 다 키운 뒤, 순차적으로 크기비교를 통해 남은 애벌레의 크기를 정해주면 되었다. 소스코드 #include #define endl "\n" #define MAX 700 using namespace std; int n, m; int zero = 0; int one = 0; int two = 0; long long arr[MAX][MAX]; long long backup[MAX][MAX]; void grow() { int y = n - 1..

https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 전형적인 백트래킹으로 푸는 문제였다. 우선, 부메랑은 다음과 같이 4가지 모양을 가질 수 있고, 이를 최대한 많이 사용하여 최대 강도를 만들어 내야 한다. 문제 해결 방법 예를들어 첫번째 부메랑을 만들기 위해서는가운데(y, x)를 기준으로 (y,x-1) 과 (y+1, x)가 범위 내에 있어야 하고 (y,x-1)과 (y+1, x)가 사용된 적이 없어야 한다. 나머지 부메랑들도 마찬..

문제의 조건은 간단했지만 dp와 dfs가 합쳐진 문제였다. 처음에 dp같지 않은 dp를 사용했더니 시간초과가 발생했다. dp[i][j]의 값을 i,j 위치에 판다가 있을 경우, 살 수 있는 최대일수 로 설정하였다. dfs의 탈출 조건을 설정해주는게 중요하다고 생각한다. if (dp[y][x] != 0) return dp[y][x]; dp[y][x]가 0이 아니라는 것은 해당 위치에 판다가 놓여졌을 때 살 수 있는 최대일수가 결정되었다는 뜻이다. 그러므로, [y][x]위치에 방문을 하였을 때 살 수 있는 일수를 계산하지 않고 그 값을 사용하면 되는 것이다. 소스코드 #include #include #define endl "\n" #define MAX 500 #define pii pair using name..

https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 이분탐색을 활용하는 문제였다. 단순히 이분탐색 뿐 아니라 파라메트릭 서치를 사용하여야 한다. 물론 이 문제는 N의 값이 작아서, 이분탐색을 활용하지 않아도 된다. 문제는 현재 세워진 휴게소들 사이에 M개의 휴게소를 세우고 휴게소가 없는 구간의 ..