본문 바로가기
728x90

전체 글

 (229)
[백준][KOTLIN][7576] 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀이 1. 주어진 토마토 정보에서 토마토가 있는 칸을 기준으로 BFS 를 수행한다. 이때 토마토가 들어있는 칸 인접 칸들은 동시에 익기 때문에 해당 부분을 고려해서 토마토 정보에서 토마토가 있는 칸(1)을 저장하는 ripenList Queue 를 선언한다. 2. ripenList 에 있는 queue 를 탐색할때 마다 result 를 증가 시킨다. 3. tomato 정보가 범위..
[백준][KOTLIN][13023] ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 풀이 1. 주어진 친구 관계를 저장하는 인접 리스트 배열을 선언한다. (val friend = Array(N) { ArrayList() }) 2. 친구의 수 0 부터 N-1 까지 반복하여 DFS 로 탐색한다. 이때 처음 시작되는 친구는 방문했으므로 visit[i] 를 true 로 설정하고 DFS 탐색한다. 3. depth 가 4 일 경우 주어진 조건과 같은 친구 관계가 되었으므로 결과를 1로 출력하고 그외에는 0으로 출력한다. 코드 import java.io.* private var result ..
[백준][KOTLIN][14391] 종이 조각 https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 문제 풀이 1. 처음에는 N, M 중 큰 값을 기준으로 자르면 무조건 최대 값인줄 알고 풀었다. 반례가 있다는 것을 알지 못했는데 아래의 경우 길이를 길게 자른다고 최대가 되지 않는다. (가로 4, 세로 3으로 짤라야 최대 값이 나온다. 2. N, M 의 최대 값이 4이고 가로/세로 반복이므로 2^(N * M) 의 경우의 수를 가진다. 3. 모든 경우에 대해서 완전 탐색을 수행한다. (i : 행..
[백준][KOTLIN][2529] 부등호 https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 문제 풀이 1. 주어진 입력을 DFS 를 이용하여 완전 탐색 한다. 2. 이때 입력된 부등호에 따라 이전 result 에 저장된 마지막 숫자와 입력으로 들어오는 숫자의 크기를 비교하여 result 에 넣을 수 있는 값인 지 확인 한다. 3. result 크기가 k + 1 일 때 최대/최소 값을 비교하여 저장한다. 이때 최소값의 경우 예제에서 0이 들어가므로 String 으로 저장하고 9자리 숫자..
[백준][KOTLIN][15661] 링크와 스타트 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 문제 풀이 1. 14886 과 유사한 문제로 팀을 나눌 때 동일한 인원 수가 아닌 한 팀이 1명에서 부터 (N-1)명까지 팀이 될 수 있는 부분을 추가한다. 코드 import java.io.* var result15661 = Int.MAX_VALUE fun main(args: Array) { val br = BufferedReader(InputStrea..
[백준][KOTLIN][14889] 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 풀이 1. 팀의 수 N 에 대해서 N/2 의 개수를 구하는 조합의 경우의 수를 DFS 를 이용하여 구한다. 2. visit 배열을 이용하여 방문된 index 를 startTeam 이라고 생각하고 방문하지 않은 index 를 linkTeam 이라고 생각한다. 2-1. 내가 짠 코드에서는 방문 배열 visit 를 이용하지 않고 startTeam/linkTeam 을 List 에 저장하여 코딩하여 좀 더 복잡해 졌다. ..
[백준][KOTLIN][14501] 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이 1. 문제에서 주어지는 N 이 15까지 주어져 있다. 2. 2^15 을 다 탐색해도 1억이 넘지 않아 시간 초과가 발생하지 않으므로 DFS 를 통해서 완전 탐색한다. 3. 탐색 시 2가지 경우에 대해서 탐색 한다. 3-1. 면담을 시작할 경우 : DFS(Day + T[Day], Sum + P[Day]) 3-2. 면담을 하지 않고 다음 날로 넘어간 경우 : DFS(Day + 1, Sum) 4. 3번의 과정을 모두 탐색하고 Day 가 N보다 크거나 같을 경우 면담을 완료하고 퇴사를 한 경우이므로 최대 값인 지를 결과에 저장한다..
[백준][KOTLIN][1759] 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 풀이 1. 주어진 입력 문자열을 오름 차순으로 정렬 한다. 2. 정렬된 문자열을 DFS 를 이용하여 완전 탐색 한다. 이때 암호 중 acis 왕 acsi 는 같은 경우로 판단하기 때문에 DFS 탐색 시 탐색 index 를 0 이 아닌 다음 탐색 index 를 시작으로 한다. 3. 결과 출력 시 최소 모음 1개 이상이고 자음 2개 이상인 지 확인 후 결과를 출력한다. 코드 import java.io..

티스토리툴바