문제 풀이

[백준] 10156 - 개미 (자바/Java)

문제 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다. 위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매 시간마다 (6,4), (5,3), (..

[SWEA] 1216 - 회문 2 (자바/Java)

처음에는 각 행과 열에서 0과 99에서 시작해서, 두 값이 같으면 start와 end를 1씩 감소 시키고, 아닌 경우에는 start와 end 중 하나만 감소시키며 검사하려고 하였는데, 재귀로 구현하였더니 case가 너무 많고 예외처리가 잘 안되어서 무한 루프가 일어났다. 두 값이 같지 않을 경우 start를 1 증가시키거나, end를 1 증가시키면서 값을 찾아야 하는데, 그 과정에서 최대 길이인 회문을 찾는 과정을 보장하지 못하였다. 그래서 이중 for문에서 값을 하나하나 돌며, 해당 index값을 중앙값으로 하는 최대 회문의 길이를 찾고, 그 중 가장 긴 회문의 길이를 반환하였다. 이 과정에서 회문의 길이가 홀수, 짝수인 경우가 있는데, 홀수인 경우는 해당 index에서 일정값만큼 빼고 더해주며 회문을..

[백준] N과 M (자바/Java) 순열, 조합, 중복순열, 중복조합

N과 M은 순열, 조합, 중복순열, 중복조합을 연습할 수 있는 문제이다. 순열과 조합은 재귀를 사용하여 풀 수 있다. 1. 순열 순열에서 nPr은, N개의 수에서 가능한 r개의 수를, 순서대로 나열하는 것이다. 순열에는 순서가 존재하기 때문에 1 2 3과 3 2 1은 다른 경우로 취급한다. 이를 재귀와 dfs를 활용하여 풀면 다음과 같다. cnt는 dfs의 깊이를 의미한다. cnt가 M이 되면 M개의 순열이 완성되었다는 의미이므로 함수를 return 한다. 또한 순열은 중복을 허용하지 않기 때문에 순열에 포함되었는지 여부를 확인할 boolean check 배열이 필요하다. 배열의 처음부터 for문을 돌며 방문하지 않은 노드일 경우 check를 true로 바꾸고, 다시 깊이 cnt를 +1 한 다음, 재귀적..

[백준] 2527 - 직사각형 (자바/Java)

문제 2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x, y)와 오른쪽 위 꼭짓점 좌표 (p, q)로 주어진다. 이 문제에서 모든 직사각형은 두 꼭짓점의 좌표를 나타내는 4개의 정수 x y p q 로 표현된다. 단 항상 x

[SWEA] 1210 - Ladder (자바/Java)

사다리타기에 따라 정답으로 이어지는 시작점을 찾는 문제다. 정답에서부터 위로 올라가는 방식으로 구현하면 된다. 먼저 목적지의 row, col 좌표를 변수에 설정하고, 오른쪽이나 왼쪽 그리고 위로 올라가도록 구현한다. 이때 주의할 점은 위로 가는 것보다 오른쪽 왼쪽이 1인지를 먼저 검사해야 한다. 오른쪽, 왼쪽으로 가고 있다면 반대방향으로 돌아가서는 안된다. 이때 2를 고려하지 않아서 무한루프에 빠지는 문제가 발생했다. 그래서 dir 변수를 지정해줘서 오른쪽, 왼쪽으로 가는 경우는 반대방향이 아닐 경우에만 이동하도록 설정하였다. package SWEA0811; import java.util.Scanner; public class SWEA_1210_Ladder { static int[][] ladder = ..

[SWEA] 5432 - 쇠막대기 자르기 (자바/Java)

이 문제는 '(' 와 ')' 가 연속해서 나올 때는 레이저고, 나머지는 막대로 생각하면 된다. 그러면 입력을 세 가지로 구분할 수 있다. 1. '('가 나오는 경우: 이때는 막대인지 레이저인지 구분할 수 없다. 2. '(' 다음에 바로 ')'가 나오는 경우: 이 경우는 레이저이다. 3. ')' 다음에 ')'가 나오는 경우: 이때는 막대이며, 한 막대가 여기서 끝남을 알려준다. 1의 경우 막대인지 레이저인지 구분할 수 없으니, 일단 bar의 개수에 더한다. 2의 경우는 레이저인게 분명하다. 더해주었던 bar의 개수에서 1을 빼주고, 레이저가 있으면 막대가 두 개로 분열되는 것이니 막대의 수만큼 sum에 더해준다. 3의 경우 막대가 끝났음을 알려주는 것이니 bar에서 1씩 빼준다. sum은 전체 막대의 개수..

[SWEA] 6190 - 정곤이의 단조 증가하는 수 (자바/Java)

주어진 N개의 수에서 가능한 두 수의 곱 중, 가장 큰 단조 증가 수를 찾는 문제이다. 먼저 가능한 두 수의 곱을 이중 for문으로 찾고, 그 수가 단조 증가하는지를 찾으면 된다. 단조 증가 여부를 찾기 위해 정수형 숫자를 String으로 바꿔주고, 각 자리수를 돌며 앞의 자리수가 뒤의 자리수보다 클 경우 false를 return하였다. 또한, 단조 증가하는 수가 없을 경우 -1을 출력하기 위해, result의 초기값을 -1로 설정하였다. package SWEA0811; import java.util.Scanner; public class SWEA_6190_단조증가 { public static void main(String[] args) { Scanner sc = new Scanner(System.in)..

[SWEA] 1954 - 달팽이 숫자 (자바/Java)

2차원 배열의 순회를 활용한 문제이다. while 문을 활용해서 해당 방향의 index를 채우고, array의 끝을 만나거나 이미 방문된 노드를 만났을 때는 방향을 바꾸어 주었다. 각 방향을 1~4로 두고 switch문으로 케이스를 정하였다. case 1: 오른쪽으로 이동: row는 그대로, col을 증가 case 2: 아래로 이동: col은 그대로, row를 증가 case 3: 왼쪽으로 이동: row는 그대로, col을 감소 case 4: 위로 이동: col은 그대로, row를 증가 그리고 1에서 더 나아갈 방향이 없으면 2로, 2에서 3으로 재귀적으로 snail함수를 수행하도록 하였다 그리고 함수를 실행하였을 때 이미 그 칸이 칠해져있다면, 모든 칸이 칠해진 경우이므로 return으로 종료조건을 주었..

[백준] 2567 - 색종이 2 (자바/Java)

문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다. 입력 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 ..

[백준] 2407 - 조합 (자바/Java) BigInteger 클래스

문제 nCm을 출력한다. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) 출력 nCm을 출력한다. 굳이 재귀로 팩토리얼을 구하지 않아도 간단하게 풀 수 있지만, 수의 범위가 커서 BigInteger 클래스를 사용해야 한다. package BOJ0809; import java.math.BigInteger; import java.util.Scanner; public class BOJ_2407_조합 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); BigInteger n = new BigInteger(Integer.toString(sc.nextInt())); BigInteger ..