목록전체 글 (27)
clap0107
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이: 문자열 문제여서 간단히 R과 D의 개수만 새고 나중에 몰아서 처리하려고 했다. 계속 틀려서 뭐가 문제인지 구글링을 해보니 R을 하고 D를 할 때마다 삭제하는 문자들이 달랐다. 예를 들어 [1, 2, 3, 4]라는 배열을 RDRD 한다고 생각하면 [4, 3, 2, 1] -> [3, 2, 1] -> [1, 2, 3] -> [2, 3]이 된다. 처음 생각한 방법으로 하게 되면 R 2개 D 두 개 이기 때문에 [1, 2, 3, 4] -> [3, 4]라는..
https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 풀이: 촌수의 개념을 잘 몰라서 계속 틀렸다. 형제지간은 2촌, 부모는 1촌, 조부모가 2촌, 부모의 형제가 3촌, 부모의 형제의 자녀가 4촌이었다. 구글에서 촌수표를 참고하면 이해하기 쉽다. 그리고 입력값이 양방향인 점을 까먹으면 안 된다. 저번에도 백준 문제들은 양방향 입력인 것을 배웠는데 또 까먹었다. 백준 예시 입력값에서는 작은 수가 왼쪽에 나오고 큰 수가 오른쪽에 나온..
https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 풀이: 쉬운 문제인 줄 알았는데 문제를 제대로 안 읽어서 시간이 좀 걸렸다. 내가 생각한 방법으로는 num이라는 변수를 0부터 1씩 while loop에서 계속 증가시키고 num을 문자열로 변환해 주었다. 다음에 6이 들어간 문자열의 index를 배열에 저장한 뒤 문자열의 index, index+1, index+2가 모두 6일 경우에 target이라는 변수를 1씩 증가시켜 주었다. 그리고 tar..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이: 처음에 이 문제를 보고 어떻게 풀어야 할지 고민을 하다 배열을 총 4개 만들어 주기로 결정했다. 지나온 횟수를 저장하는 배열, 지나온 알파벳을 저장하는 배열, 지나온 횟수 중 가장 높은 값을 저장하는 배열, 입력 값을 저장하는 배열. dfs를 실행하여 각 경우의 수마다 그전에 지나온 index가 지닌 지나온 알파벳을 복사해 왔다. 그리고 지나온 횟수를 저장하고 새롭게 지나온 알파벳을..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 설명: 처음에 이 문제를 봤을 때는 14502번 연구소 문제처럼 모든 경우의 수의 벽을 부수고 bfs 탐색을 반복하는 방법(백트래킹?)으로 풀려고 했었다. 하지만 연구소 문제와 다르게 테스트 케이스의 최대 개수가 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이고 시간제한은 2초였다. 아직도 시간 계산에 익숙하지 않아서 구글링의 도움으로 시간복잡도를 계산해 ..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이: bfs를 사용해야 한다는 것은 눈치챌 수 있었지만 벽을 놓는 조건을 어떻게 구현해야 할지 생각하느라 어려웠다. 처음에는 규칙이 존재하는 줄 알고 조건을 하나하나 적으려고 했지만 경우의 수가 너무 많음을 깨달았다. 그래서 벽을 쌓고 bfs로 탐색하는 과정을 계속 반복하여 모든 경우의 수를 체크하는 방법을 생각했지만 뭔가 이렇게 되면 시간 초과가 날 것 같았다. 그리고 모든 경우의 수를 고려하여 벽을 쌓는..