조용하지않는개발Blog

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 이러한 구현 문제는 완벽하게 구현만 하면 된다. 그전에 설계를 위해 조건을 잘 찾고 어떤 자료형을 쓸 것 인지 잘 파악하는 것도 중요하다. 처음에 문제를 읽고 이해하는데 시간이 많이 걸렸다. 하지만 조건은 간단하였다. 벨트와 로봇이 있고 벨트는 해번 한번 움직이고 로봇을 위에 올라가서 앞으로 전진할수있다는 것! 이제 조건을 정리 하였다..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 두개의 선거구로 나누어져야하고 2개이상으로 나누어지거나 선거구가 하나인 경우는 -1로 만들기만 하면 된다. 또한 그 둘의 차이가 최소인 값을 찾기위해 반복해서 돌리면 결과가 나온다! 조금 코드 짜는데 어려울수있지만 이해하면서 풀다보면 풀 수 있다. package baekjoon17471; import java.io.BufferedReader; import java.io.Inpu..

https://www.acmicpc.net/problem/1263 1263번: 시간 관리 진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다. 진영 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제를 보면 알 수 있는 부분으로 모든 일을 처리해야며 최대한 늦게 일을 시작하게 만들면 되는 문제이다. 최소 쪽을 정렬하던 최대쪽을 정렬하면 될것같은 문제인데 나는 S를 최대로 하여 정렬하였다. S의 시안에는 일을 처리해야하기 때문에 이것을 기준으로 잡았다. S의 시에서 T시간을 뺀 값(result)을 다음에 할일을 할 수 있는 시간이 되는 것이다. 다음으..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제를 보고 조합 형식으로 풀어야하나 했지만 큰값만 잘 찾아놓으면 풀수 있는 그리디 문제였다. 자리수가 큰를 찾아서 리스트로 정리해놓는다. 예를 들어 GCF + ACDEB 라고 하면 ACDEB GCF 여기서 두 값을 더하려 위치에 맞게 값을 넣으면 A = 10000 C = 01010 D = 00100 G = 00100 E = 00010 B = 0000..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제에서 이야기하는 조건과 bfs만 알고 있으면 풀 수 있는 문제이다. 다만 시간을 줄이기 위해서는 여러가지 공부가 필요할듯하다. 문제 내용을 잘 보면 옆의 나라의 인구 차이가 L과 R 사이에 있다면 같이 공유한다고 한다. 이를 생각하여 연결된 모든 국경 인원을 저장하고 나라 수 만큼의 평균을 만들고 기존의 그래프에 저장 시키면 된다. 이를 ..

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제 자체는 어렵지 않은 문제였다. 하지만 어떻게 풀면 시간초과도 날수있으니 조금 생각하며 풀어봐야하는 문제였다. 먼저 왼쪽끝에서 오른쪽 끝으로 움직이면서 큰 값만을 이동 시키면 되는 문제이다. 이를 담을 DP를 만들어 주면 된다. 나는 이를 추가한다는 느낌이 들어 stack이라고 정의하고 넣으면서 진행했다. 결과적으로 오른쪽 아래에 도착하게..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 총 4가지를 생각하여 구현하면 조금이나마 쉽게 풀리는 문제 1. 궁수가 총 3명이기에 조합을 통해 3명의 자리를 만들어 준다. 2. 적들은 한턴에 한칸씩 내려온다. 3. 적을 공격할때 왼쪽이 먼저 공격하게 만든다. 4. 이를 모두 수행하고 끝나면 적을 제거한 최대 수를 나오게 구현한다. import java.io.BufferedReader; import java.io..

https://www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 이전에 풀었단 2048(Easy) 문제에 5개의 경우를 10번 이동 했을때로 좀 더 반복하는 수가 늘어난 문제이다. 당연히 그대로 푼다면 간단하게 구현하였기에 시간초과가 날 것이다. 잘 짰다면 이부분도 잘 통과했겠지만 ㅠㅠ 그래서 시간을 줄이기위해 깊은 복사하는 부분을 최대한 줄였다. 이전에는 왼쪽, 오른쪽, 위, 아래 방향을 ..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 2048을 구현하는 문제로 왼쪽, 오른쪽, 아래, 위로 움직이는 함수를 우선 만들었다. 그리고 그래프의 결과가 얕은 복사여서 다른 방향으로 움직일때 문제가 생길 수 있어서 깊은 복사 하는 메서드를 만들었다. 이렇게 구현한 방향을 총 5번 반복할수있는 dfs를 만들면 끝이나는 문제였다. 여기서 방향에 맞춰 움직이는 것이 어려웠지 ..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 왼쪽에서 오른쪽으로 가는 선을 겹치지 않고 오른쪽 방향으로 위, 가운데 아래로 움직이며 끝까지 가게 하였을때 최대로 갈수있는 개수를 찾는 문제이다. 처음 봤을때 dfs로 풀면 되겠다. 끝까지 가는 것을 확인하고 백트래킹을 하면 되겠다 생각을 했다. 하지만 그렇게 구현을 하면 너무 많은 반복을 하게 된다. R이 10000이고 C는 500이나 되기에 무조건 시간 초과가 난다...