connecting the dots

문제 www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다. www.acmicpc.net 풀이 할머니가 1일째에 받은 떡의 개수를 A개, 2일째에 받은 떡의 개수를 B개라고 하였을 때, D일째에는 ?*A + ?*B 개일 것이다. 또한 D일째에는 D-1일과 D-2일째의 떡의 개수를 합한 개수이다. 따라서 A와 B를 기준으로 1일부터 D일까지 식을 세워나간 뒤에 D일 째에 방정식을 풀어 정수인 A, B를 찾아내고 return 하도록 구현했다. 처음 설계 수정사항 / K 자체를 코드에서 수정해주..

문제 풀이 설계 어제 풀었던 최적경로 문제와 비슷해서인지 특별한 문제 없이 풀 수 있었다 / 사실 bfs 써서 가까운 치킨집을 찾으려다가 어차피 폐업시키지 않을 치킨집 최대 개수가 13이라 모두 비교했다 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { // 치킨 배달 static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int[][] ma..

문제 www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 뱀이 사과를 먹으면 길이가 늘어나고, 주어진 시간과 방향대로 방향을 전환해야 하는 문제 / 종료 조건은 뱀이 범위를 벗어날 때와 자기 자신의 몸과 부딪힐 때 길이가 1인 사람? 동물? 이 움직이는 시뮬레이션만 하다가 뱀처럼 길이가 긴 친구를 움직이려니 감이 잘 안 잡혔다.. 처음에는 풀지 못했고, 친구와 스터디를 진행한 후에 뱀이 지나가고 있는 위치를 큐에 넣어두는 방법을 알게 됐다. 뱀이 이동하는 방식은 ..

문제 풀이 김대리가 회사에서 출발해 N명의 고객의 집에 방문한 뒤에 집까지 도착할 때까지의 경로 중 최소인 값을 구해야하는 문제이다. 김대리 기준으로 가까운 고객의 집부터 방문한다고 해서 최종 답이 나오는 것은 아니므로 주의해야 한다. N명 고객을 기준으로 순열을 만들어 모든 경우의 수를 따져본 뒤에 최종 답을 구해야 한다. 풀이 순서는 다음과 같다 N명의 고객을 기준으로해 N!개의 순열을 만들어 모든 경우를 따져본다 정해진 순서를 바탕으로 고객의 집에 방문한다 고객의 집에 방문할 때마다 거리를 count 해주고 김대리의 위치도 옮겨준다 고객의 집에 모두 방문하고 나면 김대리 집까지의 최소 경로도 더해준다 다음 순서로 경로를 구하기 위해 김대리의 위치를 처음 위치로 돌려놓는다 모든 순열에 대해 2~6번을..