본문 바로가기

분류 전체보기

 (386)
[boj] 백준 2293 동전1 - 동적프로그래밍 [문제] https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 동적 프로그래밍 문제이다. coin 배열에 동전의 가치들을 저장해두고 dp[a] = b에 대해 a원을 만들 수 있는 경우의 수 b로 두고 접근한다. 0원을 만드는 경우의 수도 1가지이므로 dp[0] = 1로 둔다. 동전의 가치가 1, 2, 5가 있고 10을 만들 수 있는 경우의 수를 구한다고 하자. 동전 1에 대해서 1을 만들 수 있는 경우의 수는 0을 만들 수 있는 경우의 수와 ..
[boj] 백준 2023 신기한 소수 - DFS [문제] https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net [풀이] dfs로 풀 수 있다. 왼쪽에서 1번째, 2번째 ... n번째 자리까지의 수가 모두 소수여야 하므로 처음 올 수 있는 수는 소수인 2, 3, 5, 7 밖에 없다. 이 수들에 대해서 짝수는 소수가 아니므로 홀수를 대상으로만 수를 덧붙여 소수 판별을 해주고, 소수인 수들에 대해서 n자리가 될 때까지 반복한다. [코드] #include #include #include #in..
[boj] 백준 1916 최소비용 구하기 - 다익스트라 [문제] https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net [풀이] 다익스트라 알고리즘. 우선순위 큐를 이용해 풀이하였다. [코드] // Created by strit on 2022-02-23. gold5 1916 최소비용 구하기 - 다익스트라 #include #include #include #include #define INF 987654321 using namespace::std; int n, m; int d..
[boj] 백준 1461 도서관 - 그리디 [문제] https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net [풀이] 그리디 알고리즘. 책을 원래자리에 돌려놓기 위해서는 어차피 원점을 지나야 하므로 음수, 양수를 따로 나눠서 계산해준다. m권을 한꺼번에 옮길 수 있다면 왕복값은 m권 중 더 큰 값의 왕복값으로 계산해준다. 그 후, 양 극단에 있는 값 중 더 큰 값에 대해서, 갖다 놓기만 하면 되므로 편도로 계산해주기 위해 값을 빼준다. 예를 들어, -39 -37 -29 -28 -6 2 11 에 대해서..
CH7(7.3). 컬렉션과 범위에 대한 관례 1. 인덱스로 원소에 접근: get과 set - 인덱스 연산자도 관례를 따른다. 인덱스 연산자를 사용해 원소를 읽는 연산은 get 연산자 메소드로 변환되고, 원소를 쓰는 연산은 set 연산자 메소드로 변환된다. operator fun Point.get(index: Int): Int{ return when(index){ 0 -> x 1 -> y //주어진 인덱스에 해당하는 좌표를 찾는다. else -> throw IndexOutOfBoundsException("Invalid coordinate $index") } } >>>val p = Point(10, 20) >>>println(p[1]) 20 data class MutablePoint(var x:Int, var y:Int) operator fun Mut..
[boj] 백준 1107 리모컨 - 브루트포스 [문제] https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net [풀이] 범위가 크지 않아 브루트포스 완전 탐색 방식으로 해결할 수 있다. 이동하고자 하는 채널은 0 m; for(int i=0; i> a; broken[a] = true; //고장난 버튼 } if(n==100) cout
[boj] 백준 1759 암호 만들기 - DFS [문제] https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net [풀이] dfs를 이용해서 풀 수 있다. 증가하는 순서의 배열로만 암호가 만들어지므로 알파벳을 정렬 후 사용한다. depth가 암호의 길이가 되었을 때 모음과 자음의 개수를 확인해주고 조건에 일치하면 출력한다. [코드] // Created by strit on 2022-02-17. gold5 1759 암호 만들기 - dfs #include #include #include using namesp..
[boj] 백준 1188 음식 평론가 - 최소 공약수 [문제] https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net [풀이] 소세지가 하나로 이어져 있다면 m명의 평론가에게 나누어 주기 위해서는 m-1번 잘라야 한다. 그런데 소세지가 여러개인 경우 이미 잘라져 있는 것이기 때문에 중복된 부분을 제거해야 한다. 예를 들어 3개의 소세지를 6명의 평론가가 나눠먹는다면 둘의 최대 공약수인 3-1=2만큼 이미 잘라져 있는 것이다. 1개로 연결된 소세지였다면 6-1=5번 잘라야 하지만 이미 2번 잘라져있다고 여겨 5-2=3만큼만 더 자르면 된다. 즉 m-1-(gcd(n,m)-1) = m-gcd(n,m)이 된다. (..

티스토리툴바