본문 바로가기

전체 글

 (265)
백준1062 - 가르침 www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 백트래킹을 이용하여 구현하였다. a, n, t, i, c는 무조건 주어지므로 5개 이상 배우지 않으면 단어를 배울 수 없게 된다. 따라서 5개 이하는 탐색을 하지 않고 0을 출력한다. 26개 경우는 모든 알파벳을 배우므로 단어를 모두 읽을 수 있다. 따라서 단어의 개수를 출력한다. 그 외의 경우는 a, n, t, i, c의 갯수를 주어진 K에서 빼서 백트래킹을 할 때 마다 탐색을 한다. 그러면 처음에 5..
백준1089 - 엘리베이터 https://www.acmicpc.net/problem/1089 1089번: 엘리베이터 가능한 것은 8, 9, 88, 89 www.acmicpc.net 약간의 노가다가 필요한 문제이다. 0부터 9까지 숫자를 디지털로 표현하여 저장하고 입력한 숫자를 한개씩 비교하며 해결한다. 입력한 숫자에는 표시가 되있지만 찾으려는 숫자에는 표시가 되어있지 않았다면 그 숫자는 표현할 수 없다고 한다. 숫자를 구할 때는 현재 자릿수를 제외하고 모든 자릿수의 수의 경우의 수를 곱하여 구한다. ex.) 3 ..#.#.#...# ..#...#...# ..#...#..## ..#...#...# ..#...#...# 첫번째 숫자는 가능한 경우가 0, 1, 3, 4, 7, 8, 9 두번째 숫자는 가능한 경우가 0, 3, 4, 7, ..
백준18115 - 카드 놓기 https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. � www.acmicpc.net deque를 이용하여 해결한 문제이다. deque를 선택한 이유는 문제에서는 맨 앞이나 맨 뒤나 맨 뒤에서 2번째 수를 뽑아내는 연산을 하고 있어서 deque를 선택하였다. 주어진 입력과 반대로 거슬러 올라가면서 추리한다. 주어진 입력이 1인 경우는 맨 뒤에 원소를 넣어준다. 주어진 입력이 2인 경우는 맨 뒤에 원소를 빼내어 어딘가에 저장해두었다가 현재 넣어야 하는 수를 맨 뒤에 넣고 다시 빼..
백준1174 - 줄어드는 숫자 https://www.acmicpc.net/problem/15729 15729번: 방탈출 첫째 줄에 N(1 ≤ N ≤ 1,000,000)가 주어지고 둘째 줄에는 쪽지에 적혀 있는 N자리의 수가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net bfs를 이용하여 내림차순으로 구성되있는 수를 찾아내는 문제다. 처음에 0~9까지의 수를 큐에 넣어주고 현재 수의 일의자릿수 보다 작은 수가 있으면 탐색해나가는 형식으로 구현하였다. 숫자가 커질수 있어서 long long int를 사용하였다. #include #include #include #include using namespace std; int N; int limit; vector v; void bfs() { int cnt = 0; queue q; ..
백준2780 - 비밀번호 https://www.acmicpc.net/problem/2780 2780번: 비밀번호 각각의 Test case에 대해서 조건을 만족하는 비밀번호의 개수를 출력하라. 단, 수가 매우 커질 수 있으므로 비밀번호의 개수를 1,234,567으로 나눈 나머지를 출력하라. www.acmicpc.net 간단한 DP문제였다. 숫자의 위치를 보고 직전에 있던 숫자가 바로 뒤에 나오는 경우를 더해서 1,234,567로 나눠준 뒤 출력할 때 모두 더하여 다시 한번 1,234,567로 나눠주면 된다. #include using namespace std; int T, N; int mat[1001][10]; void setting() { for(int i = 0; i > N; for(int i = 0; i < 10; i++) ..
백준17178 - 줄서기 https://www.acmicpc.net/problem/17178 17178번: 줄서기 아이즈원의 팬인 시온이는 드디어 티켓팅에 성공하여 콘서트를 갔다. 콘서트장에 일찍 도착한 시온이는 기대하며 입장을 위해 줄을 섰다. 하지만 아이즈원의 인기대로 시온이를 포함한 많은 �� www.acmicpc.net 스택과 큐와 우선순위 큐를 이용하여 풀었다. 우선 5개씩 입력을 큐에 넣었고 입장 순서를 구하기 위하여 우선순위 큐에 넣었다. 현재 순서를 구하기 위한 과정은 다음과 같다. 1. 현재 순서를 대기열에서 발견한 경우는 스택에서 마지막 원소를 뽑는다. 2. 현재 순서를 줄에서 발견한 경우는 큐에서 첫번째 원소를 뽑는다. 3. 현재 순서를 대기열과 줄에서 발견하지 못한 경우는 스택에 대기열 첫번째 원소를 넣는다..
백준11779 - 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스� www.acmicpc.net 다익스트라를 이용하여 푼 문제이다. 특별한 점은 경로를 출력해야 된다는 것이다. 출발 노드에서 도착점으로 향하는 맵을 최대 도시의 갯수로 구성하여 더 짧은 경로가 들어오면 경로를 바꿔주는 형식으로 문제를 해결하였다. #include #include #include #include using namespace std; int n, m; int x, y, z; int..
백준2023 - 신기한 소수 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수� www.acmicpc.net 우선 2, 3, 5, 7이 한자리 소수니까 해당 숫자에서 탐색을 시작한다. 2자리 수부터 마지막 자리로 짝수가 오면 소수가 아니니까 홀수만 판단한다. 소수를 판단 할 때는 해당 숫자의 루트값을 구하여 자연수를 끝 값으로 바꾼 뒤 3부터 끝 값까지 홀수만 탐색해 나가는 방식을 썼다. 소수로 판단하는 숫자는 무조건 홀수만 매개변수로 넘어가기 때문이다. #include #include us..

티스토리툴바