https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 제목 그대로 정석 최단거리 구하기인데 문제 조건을 빠뜨리기 쉬워 한 번 틀렸습니다 를 받았다. 최단 거리 구하기 Queue를 사용한 BFS로 구현 가능하다. 시작은 입력값이 2인 위치부터이고, 도달하는 데에 걸린 시간을 추가해서 돌려주면 된다. 방문 체크와 시간을 동시에 확인하고 싶어서 cost라는 배열을 만들었다. 처음 입력값을 받으면서 cost의 원..
분류 전체보기
https://www.acmicpc.net/problem/25757 25757번: 임스와 함께하는 미니게임 첫 번째 줄에는 사람들이 임스와 같이 플레이하기를 신청한 횟수 $N$과 같이 플레이할 게임의 종류가 주어진다. $(1 \le N \le 100\,000)$ 두 번째 줄부터 $N$개의 줄에는 같이 플레이하고자 하는 사람들 www.acmicpc.net 필요한 인원 수 고르기 게임이 윷놀이("Y")면 2명, 같은 그림찾기("F")면 3명, 원카드("O")면 4명이서 게임을 진행한다. 주인공 임스는 항상 게임에 참여하므로, 더 필요한 유저는 각각 1, 2, 3명인 셈이다. 여러가지 방법이 있겠지만, 삼항연산자를 연습해보고 싶어서 다음과 같이 작성했다. String game = st.nextToken(); ..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 동생이 수빈이보다 낮은 숫자에 있는 경우 (N > K) BFS를 시도하기 전에 먼저 생각해둬야 할 것이 있다. 동생이 있는 K가 수빈이가 있는 N에 비해 작은 수라면 어떻게 될까? 이동할 수 있는 경우의 수가 한 칸 전진, 숫자가 두 배인 칸 가기, 한 칸 후퇴 세 가지밖에 없는 상황에서, K가 더 작다면 수빈이는 매번 -1만 진행해야 한다. 앞으로 한 칸을 ..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 스스로를 지목한 사람 처리 가장 먼저 생각한 것은 "자기 자신을 지목하는 사람을 포함해서는 절대 사이클이 이뤄지지 않는다"였다. 스스로를 지목한다면 혼자 프로젝트를 하는 것으로 미리 표시하기로 했다. 그 사람을 포함해서는 팀을 만들 수 없기 때문이다. +) 일단 이 아이디어를 가장 먼저 생각해냈고, 이 부분을 포함한 코드로 정답 처리를 받았으나 나중에 확인해보니 아래 방문 체크를 한다면 스스로를 지목한..
https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 1026번 : 보물 [수학, 그리디 알고리즘, 정렬] 이번 문제의 아이디어는 '가장 큰 수와 가장 작은 수를 곱해야 한다' 는 것이다. 문제에는 A 배열은 순서를 바꿔도 되지만 B 배열은 바꾸면 안된다고 명시해두었는데, A와 B의 곱셈을 더하는 것으로 이뤄진 이 문제에서 A 배열의 순서를 바꿀 수 있다면 B의 순서를 내버려두는 것은 큰 의미가 없다. 즉, 공식이나 순서까지 출력하라는 것이 ..
https://www.acmicpc.net/problem/11912 11912번: 격자 보존하기 승현이는 1 × n 크기의 격자판을 가지고 있습니다. 각 칸에는 1 이상 n 이하의 자연수 번호가 왼쪽에서부터 차례대로 붙어있습니다. 이 중 k개의 칸에는 말이 하나씩 놓여 있는데, 이 말들은 격자 www.acmicpc.net 11912번 : 격자 보존하기 [그리디 알고리즘, 정렬] 어떤 격자가 말에게 더러워지지 않는 경우는 두 가지를 생각할 수 있다. 1. 칸막이를 한 개 사용해야 하는 경우 : 시작 ~ 첫 번째 말 / 마지막 말 ~ 끝 2. 칸막이를 두 개 사용해야 하는 경우 : 말과 말 사이 따라서 해당 두 가지 경우를 따로 저장했다. int[] one = new int[2]; // 칸막이 하나만으로 보..
https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 이 역시 [소수의 연속합]에서 사용했던 에라토스테네스의 체를 복습할 겸 풀어보았다. 문제 자체에서 에라스토스테네스의 체를 잘 설명해주고 있다. 위 문제를 풀었을 때에는 소수가 아닌 값을 구할 때 while문을 통해 곱해주었지만, 이번에는 for문을 사용해보았다. 다른 사람의 코드를 봤을 때 이 편이 조금 더 깔끔해보였기 때문이다. 그를 바탕으로 작성한 에라토스테네스의 체는 다음과 같다. for (int i = 2; i
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 이전에 올렸던 [소수의 연속합]이라는 문제에서 투 포인터를 구현했을 때 if문과 break을 남발한 것이 마음에 걸려 같은 알고리즘의 문제를 풀어보았다. 골자는 똑같다. 구간합이 주어진 수 M과 같거나 큰 경우에는 start를 1 올리고, M보다 작은 경우에는 end를 1 올려 주어서 해당하는 arr의 값을 더해준다. M과 같은 경우에는 count도 1 더..
