목록코딩테스트 (16)
clap0107
https://www.acmicpc.net/problem/23881 23881번: 알고리즘 수업 - 선택 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 교환 횟수 K(1 ≤ K ≤ N)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 풀이: 이 문제에서는 선택정렬을 위쪽에서 시작해서 아래로 내려가는 방식으로 구현하였다. c++과 다르게 내림차순 for문이 익숙하지 않아서 구현하는데 시간이 좀 걸렸다. 그냥 의사코드를 따라서 적기만 하면 되는데 코드를 조금이라도 줄이겠다고 내 맘대로 바꾸니까 되지 않았다. 오답 코드에서 arr[j]가 arr[i]보다 크기만 하면 괜찮을 줄 알았는데 알고..
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이: 원래 100과 가까운 경우를 확인하고 아니라면 bfs로 입력과 최소 차이값을 가지는 숫자로 답을 구하려고 했었다. 하지만 그렇게 하면 예제 입력 7인 80000, 2, 8 9를 실행할 때는 이상한 값을 출력하였다. 최소 차이값으로 따지면, 허용된 버튼에서 71111이 선택되어 8894이라는 어림도 없는 답이 나오게 되었다. 예제 출력은 77777이 선택된 2228이 정답이었..
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가 지닌 지나온 알파벳을 복사해 왔다. 그리고 지나온 횟수를 저장하고 새롭게 지나온 알파벳을..