메이쁘

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 시뮬레이션 문제다. 이 문제는 뱀 문제와 비슷하다. https://maivve.tistory.com/84 (JAVA) 백준 319..

https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 시뮬레이션 문제이다. 고전 게임 중 이런 게임이 있지 않았나...? 아무튼 바로 설명 진행하겠다. 매커니즘 특이사항을 살펴보자. 1. 게임이 종..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 이건 좀 브루트 포스에 가까운 시뮬레이션 문제였습니다.. 정공법으로 for문으로 탐색해도 메모리 크게 차지하지 않더군요.. 속도도 높지 않고. 메커니즘을 포스팅할거지만 다른 사람들 풀이 방법을 보니 꼭 제가 푸는 방법이 정답이 아닐 수 있어 제가 어떤식으로 이 문제를 풀었는지 핵심만 적겠습니다! 저는 우선 크게 1) W로 시작 2) B로 시작 (인덱스가 0 부터 n - 1 까지라고 가정했을..

https://www.acmicpc.net/problem/2455 2455번: 지능형 기차 최근에 개발된 지능형 기차가 1번역(출발역)부터 4번역(종착역)까지 4개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. 이 장치를 이용하여 출발역에서 종착역까지 가는 도중 기차 안에 사람이 가장 많을 때의 사람 수를 계산하려고 한다. 단, 이 기차를 이용하는 사람들은 질서 의식이 투철하여, 역에서 기차에 탈 때, 내릴 사람이 모두 내린 후에 기차에 탄다고 가정한다. 내린 사람 수 www.acmicpc.net 첫 시뮬레이션 문제 이다. 너무 쉽다. 핵심은 1 ~ n번 역을 방문할 때 마다 이전까지의 역을 통해 탑승하고 있는 사람 수 - 이번 역에..

https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다. 조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 www.acmicpc.net 그리디 알고리즘이다. 정답률에 비해 난이도는 죠금 쉬운 편 처음에 정렬 기준을 b - a 로 잡았으나 50% 이상 가지 못하고 틀렸다..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 www.acmicpc.net 후.. 나에겐 시간 도둑인 문제였다. 상당히 헤맸어... 정답률 23%인 이유가 있었다. 처음에 가방 무게 작은 순서대로 하나씩 꺼내서..

https://www.acmicpc.net/problem/2884 2884번: 알람 시계 문제 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다. 이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다. 바로 "45분 일찍 알람 설정하기"이다. 이 방법은 단순하다. 원래 설정되어 있는 알람을 45분 앞서는 시간으로 바꾸는 것이다. www.acmicpc.net 구현 문제인데 난이도 최하. 정답률이 낮은 이유는 (나도 했었던) 한 가지 실수 때문이다. 바로 0시 45분 과 같은 경우에서 0시 0분..

https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다. www.acmicpc.net 다익스트라 문제이다. 처음에 1을 제외한 나머지를 다익스트라 알고리즘 돌렸더니 시간 초과가 발생했었다... 문제를 잘못 이해해서..ㅠㅠㅠ 1에서 ..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 그리디 알고리즘 문제. 난이도는 하! (내가 한번에 풀어서) 매커니즘 구멍의 좌우로 0.5 센치씩은 확보해야 한다고 했으므로 하나의 구멍을 메꾸기 위해서는 테이프 길이 1을 사용해야 한다. 예제를 통해 풀이 방법을 알아보면 input: 4 2 1 2 100 101 -> 테이프의 길이 : 2cm -> 2 - 1 : 1cm 좌우로 0.5cm 확보하면 구멍 1, 2를 ..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다. www.acmicpc.net 백트래킹 문제로 해결해야 할 줄 알고 했다가 시간은 4000ms 까지 치솟아서 또 다른 해설을 찾던 중 수학 문제로 접근하는 방법을 알게 되었다. (가장 최고 자리에 높은 숫자를 부여하는 그리디 알고리즘은 예외가 존재하기 때문에 안됨!) 그래서 백트래킹 방법 간단히 설명하고, 수학 문제 접근 방법으로 설명을..