SY DevLog

난이도는 어렵지 않은 문제이다. 어떤 수 N으로 나눌 때 나머지는 항상 N보다 작다. "나머지 = 몫"인 경우를 구하면 되므로 N보다 작은 수 i에 대하여 "i = 나머지 = 몫"이라고 할 때, "몫*N + 나머지"가 문제에서 구해야 하는 자연수이므로 i*N + i (단, i

https://www.acmicpc.net/problem/25501 25501번: 재귀의 귀재 각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다. www.acmicpc.net 문제 자체는 정말 쉬운 편에 속한다. 어떤 문자열이 주어졌을 때, 팰린드롬인지 아닌지 판별하는 문제인데 게다가 심지어 문제에서 재귀 함수까지 직접 짜서 준다. 재귀함수 호출 횟수도 출력해야 하기 때문에, 주어진 재귀함수에다가 카운트 변수 하나 추가하여서 호출 될 때마다 +1 해주면 끝이다. ...라고 생각했으나, 계속 5% 대에서 실패 다음 코드는 실패가 떴을 때의 제출한 코드이다. #include #include int T; int cnt; int..

1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 전체 나라 개수가 N개이고, 이어져 있는 길이 N-1개 일 때, 최소 비용으로 어느 시작 나라 하나를 정해서 모든 나라를 다 방문한 후 다시 시작 나라로 돌아오기 위해서는 나라는 2*N-1개를 방문하고, 길은 2*(N-1)번을 지나야 한다. 따라서, 각 길의 비용은 이어져 있는 두 나라의 비용 + 길의 비용*2 로 정하면 된다. 예를 들어, 1번과 2번 나라 사이의 길의 비용은 1번 나라의 비용(10) + 2번 나라의 비용(..

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 백준 2206번 : 벽 부수고 이동하기 문제와 비슷하다. 기존의 벽 부수고 이동하기 문제에서는 벽을 한 번만 부수는 게 가능했는데, 이번 문제에서는 K가 주어지면, K개만큼 벽을 부수면서 이동이 가능하다. 벽 부수고 이동하기에 대한 풀이는 아래 포스팅을 참고 https://lotuslee.tistory.com/142 [백준 2206번] 벽 부수고 이동하기 (java) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이..

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 처음에는 일반적인 너비우선탐색(BFS) 방법처럼 visited 배열을 2차원 배열로 만들어서 문제를 풀었으나, 11%에서 틀렸다고 나왔다. 특정 위치(nr, nc)에 도착했을 때, 그 위치까지 도달하는 과정에서 벽을 한 번 부수고 도달했는지, 한 번도 부수지 않고 도달했는지 이 두가지 경우를 모두 고려해서 방문처리를 해야 한다. 따라서 visited 배열을 2차원 배열이 아닌 3차원 배열로 만들어서 1. 벽을 부수지 않고 방문한 경우 :..

백준 전깃줄 문제와 유사하다. 이진탐색을 사용한 증가하는최장부분수열(LIS)을 구하는 문제이다. 다만, 수열의 길이만 구하는 것이 아니라 수열 자체도 구해야 하므로 역추적하는 배열이 별도로 필요하다. 역추적을 통한 증가하는최장부분수열의 수열 구하는 방법은 아래 포스팅에 나와있다. LIS(Lowest Increasing Subsequence) - 수열 구하기 저번 글에서는 최장 증가 수열의 길이를 구하는 경우에 대해 다루었다. LIS(Lowest Increasing Subsequence) - 길이 구하기 LIS(Lowest Increasing Subsequence) : 최장 증가 수열 : 어떤 수열이 주어졌을 때, 그.. lotuslee.tistory.com 이 문제는 전선이 만나지 않도록 하면서 전구가 ..

20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 토네이도의 방향 순서가 서쪽 -> 남쪽 -> 동쪽 -> 북쪽 순서대로 반복된다. direct 3차원 배열을 만들어서, - 첫 번째 인덱스는 방향(0: 서쪽, 1:남쪽, 2:동쪽, 3:북쪽)을 의미하고, - 두 번째 인덱스는 0일 경우 r 좌표(행 좌표), 1일 경우 c 좌표(열 좌표)를 나타내었다. - 세 번째 인덱스는 현재 위치를 기준으로 1%비율에 해당하는 위치, 2%에 해당하는 위치, 5%에 해당하는 위치, 7%에 해당하는 위..

9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net DFS와 트라이 알고리즘을 통해 문제를 해결하였다. 게임 사전에 등재된 단어들을 트라이에 넣는다. 각 보드마다 DFS방식으로 접근하면서 여태까지 지나온 알파벳들로 이루어진 단어가 트라이에 포함되어 있는지를 확인한다. 문제에서 같은 단어를 여러 번 찾은 경우는 하나로 간주한다고 했으므로 중복을 피하기 위해 찾은 단어를 HashSet에 넣어주었다. 기존의 트라이의 contains() 메서드는 true 혹은 false를 반환하였다.특정 단어에 트라이..

5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net parent라는 ArrayList 리스트 배열을 만들어서 현재 노드의 직전 노드를 저장하는 공간을 만들어주었다. 현재 노드에 최소 경로로 도달할 수 있는 직전 노드가 여러 개 있으면, ArrayList에 여러 개를 넣는다. 예를 들어, 위의 문제 예제 그림에서 D = 6에 최소 경로로 도달할 수 있는 경우의 수는 2가지이다. 이 때 각각의 경우에서 6번 노드의 직전 노드는 3번과 5번 노드이다. 따라서 parent[6]에는 {3, ..

20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net int[] A = new int[2*N+1] : 칸 별로 내구도를 의미 int[][] num = new int[2][N+1] : 각 위치에 무슨 번호의 칸이 있는지를 의미 컨테이너 벨트의 가장 왼쪽 위가 [0][1], 가장 오른쪽 위가 [0][N], 가장 왼쪽 아래가 [1][1], 가장 오른쪽 아래가 [1][N] 위치를 의미한다. 처음에는 num[0][1] = 1번 칸, num[0][2] = 2번 칸, ... num[0][N]= N번 칸 ....