Java/Algorithms

문제 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 접근 방식 맵의 최대 크기가 1000 * 1000이기 때문에 매번 벽을 기준으로 BFS나 DFS를 이용해 탐색하면 시간초과가 발생한다. 그래서 0을 기준으로 각 구역의 크기를 계산한 후에 1을 기준으로 상하좌우로 맞닿은 구역의 크기를 더해주면 되는데 이때 중복이 있을 수 있기 때문에 Set을 사용해서 처리해 주면 된다. 예를 들어 현재 벽과 맞닿은 구역이 1, 1, 2, 3 구역이라면 1 구역은 한 번만 계산하면 되기 때문에 중복을 처리..

문제 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 접근 방식 스도쿠의 빈칸을 채우는 문제다. 특별한 규칙은 없기 때문에 백트래킹으로 매번 행과 열, 3*3칸을 확인해 주며 가능한 숫자들을 모두 시도해보아야 한다. 문제의 설명이 조금 헷갈렸는데 81 자리의 수가 제일 작은 경우라는 말이 81번째 칸을 말하는 게 아니라 9*9칸을 일렬로 늘어놨을 때 나오는 81자리 수를 말하는 것이기 때문에 백트래킹 자체를 1 ~ 9까지의 수를 오름차순으로 대입하다 보면 처음 나오는 결과가 가장 작은 수이기 때문에 그 ..

문제 15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근 방식 기존의 연산자 끼워넣기 1, 2번 시리즈와 비슷하지만 연산자의 우선순위를 적용해야 해서 선택한 연산자들을 배열에 기록해 두었다 나중에 한 번에 연산을 해줘야 한다. 중간중간에 처리해서 빠르게 계산을 해보려 했는데 예제들은 통과가 되지만 제출하면 도무지 1 퍼에서 올라가질 않길래 포기하고 한 번에 연산을 해줬다. 기존 방식대로 각각의 연산자들을 선택할 수 있을 때 선택하는 방식으로 진행하..

문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 접근 방식 백트래킹으로 조건을 체크해가며 암호를 만들어주는 문제다. 암호는 다음과 같은 조건을 체크해줘야한다. 암호는 사전순으로 오름차순으로 정렬되어야 한다. 모음은 하나 이상, 자음은 2개 이상 포함되어야 한다. 그래서 입력으로 받은 문자 배열을 사전순으로 정렬한 후에 백트래킹으로 조합을 해주면서 모음과 자음을 카운트하여 파라미터로 들고 다니면 된다. 계속해서 조합을 하다 원하는 암호의 길이를 만족하면 모음과 자음수가 조건을 만족하는지 체크하고 만족하면 출력해..

문제 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 접근 방식 연산자 끼워넣기 1번이랑 다른 점은 주어진 연산자의 수가 주어진 수들보다 많을 수 있다는 것인데 기존 방식 그대로 풀어도 딱히 문제는 없다. 기존의 백트래킹 방식 자체가 애초에 모든 연산자를 다 사용해보기 때문에 수의 개수와 맞지 않아도 모두 조합해볼 수 있다. 풀이 class Main { static int n, max = -1000000001, min = Integer.MAX_VALUE..

문제 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 접근 방식 백트래킹을 사용해 0 ~ 9까지의 수들을 한 번만 사용하며 조합해가면서 주어진 부등호의 순서와 대소관계가 일치하는지 확인해주면 된다. 첫 번째 고른 숫자를 제외하고 이후에는 부등호와 이전 숫자와 현재 숫자가 일치하는지 확인해주며 진행하면 된다. 모든 숫자를 고른 후에 부등호를 비교하는 것도 상관 없지만 매번 숫자를 고를 때마다 확인하면 중간에 맞지 않는 경우에 멈출 수 있어서 좋다. k가 9인 경우 최대 값이 9876543210이기 때문에 int 타입의 변수..

문제 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 접근 방식 쉬운 조합 문제인데 문제를 잘못 봐서 헤맸다. abs(num[0] - num[1]) + abs(num[2] - num[3]) + ... + abs(num[n - 2] - num[n -1]) 가 아니라 abs(num[0] - num[1]) + abs(num[1] - num[2]) + ... + abs(num[n - 2] - num[n -1]) 인 부분을 조심해야 한다. 이 부분만 조심하면서 재귀 호출 시 파라미터로 이전까지의 계산을 넘겨주면서 백트래킹을 이용해 조..

문제 27964번: 콰트로치즈피자 치즈와 피자에 환장하는 비행씨는 매일같이 치즈피자를 사 먹다가 지갑이 거덜 나고 말았다. 만들어 먹는 것이 사 먹는 것보다 싸다는 것을 안 비행씨는 여러 가지 토핑을 가져와서 직접 피자를 www.acmicpc.net 접근 방식 토핑의 이름이 n개 주어질 때 Cheese로 끝나는 서로 다른 토핑이 4가지 이상인 경우에는 콰트로치즈피자를 만들 수 있으니 "yummy"를 그렇지 않다면 "sad"를 출력해줘야 한다. endsWith 메서드를 사용해 각 토핑이 Cheese로 끝나는지 확인하여 Set에 추가해준 후에 마지막에 Set의 사이즈가 4 이상인지 확인하면 된다. HashSet은 중복을 허용하지 않기 때문에 이런 문제에서 활용하기 좋다. 풀이 class Main { publ..