GitHubSeob

문제 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제풀이 메모이제이션을 이용했다. idx는 0부터 N-1까지, idx2는 idx부터 N-1까지로 둔다. idx는 더하려는 첫 번째 원소, idx2는 더하려는 마지막 원소이다. 따라서 idx부터 idx2까지 더한 값을 구하고, M인지 판별을 한다. 각각의 값은 자연수이므로 sum이 M을 넘어가면 더할 때마다 무조건 커지므로 효율성을 위해 break를 한..

문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제풀이 다음칸을 선택, 선택하지 않는 경우인 두 경우를 나누어 DFS함수를 실행시킨다. 선택한다면 visit함수에 push_back으로 해당 idx번째 값을 넣어준다. idx가 N-1이 되었다면 visit벡터의 값들의 합을 구해 S와 같은지를 비교한다. 모두 선택하지 않는 경우는 개수에 포함이 안되므로 visit의 size가 0이 아닐 때라는 조건을 걸어..

문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 문제풀이 다음칸을 선택, 선택하지 않는 경우인 두 경우를 나누어 DFS함수를 실행시킨다. DFS함수의 인자는 현재 위치가 로또의 몇 번째 숫자인지를 idx, 몇 개를 선택했는지가 cnt이다. 6개만 고르면 되므로 cnt가 6일 때 answer에 담은 숫자들을 출력한다. idx+1이 num보다 작을 때만 DFS함수를 실행하도록 하면 된다. 코드 #include #include usi..

문제 https://www.acmicpc.net/problem/14726 14726번: 신용카드 판별 신용카드는 총 16자리의 숫자로 구성되어 있다. 언뜻 보기에는 무작위로 된 숫자로 구성되어 있는 것 같이 보이지만 그 속에는 하나의 수학적 비밀이 숨겨져 있다. 그중 하나가 카드 번호가 유효 www.acmicpc.net 문제풀이 맨 오른쪽부터 짝수번째는 *2를 해준 뒤 10 이상이면 answer에 10을 나눈 몫, 나눈 나머지를 더해준다. 홀수번째일 때는 그냥 answer에 더 해주면 된다. 모든 자리를 확인하였으면 10으로 나눈 나머지가 있는지 없는지만 판별하여 출력하면 된다. 코드 #include using namespace std; int main() { int T(0); int idx(0); ci..

문제 https://www.acmicpc.net/problem/13419 13419번: 탕수육 출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 각 테스트 케이스의 답을 순서대로 출력한다. 각 테스트 케이스마다 첫 번째 줄에 먼저 시작한 사람이 기억해야 될 문자열 중 가장 짧은 www.acmicpc.net 문제풀이 입력받은 문자열의 길이가 짝수이면 첫 번째 사람은 짝수번째 알파벳만, 두 번째 사람은 홀수번째 알파벳만 외우면 된다. 문자열의 길이가 홀수 일 경우 추가로 상대방의 문자열을 더하면 된다. 코드 #include using namespace std; int main() { cin.tie(NULL); ios::sync_with_stdio(false); int T(0); string data("..

문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제풀이 BFS로 풀었다가 메모리 초과가 났고, DFS로 풀었다가 시간 초과가 났다. 질문글을 보니 DFS에 벡터를 넣어 벡터를 복사하게 되면 시간이 더 걸리므로 전역으로 선언하는 것이 좋다고 했다. 그 부분을 수정했더니 통과가 됐다. 크게 어려운 부분은 없다. 0, 0부터 시작하여 DFS로 모든 경우를 탐방하는데 이미 지나갔던 알파벳이 있는 곳은 가지 못하도록 조건만 걸면 된다. v..

문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제풀이 0인 좌표를 큐에 넣고 숫자를 넣었으면 큐에서 pop 하는 식으로 풀었는데 숫자가 안 채워지는 부분이 있어 틀렸다. 다른 블로그를 참고해서 풀었다. 문제풀이는 모든 경우의 수를 탐색하고, 숫자가 채워졌으면 다음 0인 칸으로 가서 다시 숫자를 채운다. 다음 칸에서 9까지 확인을 했는데 다른 부분과 겹쳐 채워질 수 없으면 다시 전 칸으로 돌아와 다른 숫자로 채운다. 이런 식으로 모든 경..

문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제풀이 DFS가 아닌 비트마스크를 이용하여 문제를 풀었다. 글자를 모두 입력받고 정렬한다. 모든 경우의 수를 돌면서 해당 글자가 자음인지, 모음인지를 확인하고, 조건들을 만족했을 때 set인 answer에 insert 했다. 반복이 종료되면 set의 원소를 모두 출력한다. 코드 #include #include #include using namespace std; int main() { ios::..

문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제풀이 다른 문제가 더 있는지는 모르겠지만 큐에 집어넣기 전에 visit과 정답을 확인하냐 안 하냐에 따라서 메모리 초과가 갈렸다. BFS로 풀었고 큐를 pair로 선언하여 현재 위치, 버튼을 누른 횟수를 push 했다. visit벡터를 이용해서 두 번 다시 같은 층을 가지 않도록 했다. 평범한 BFS문제인 것 같다. 크게 신경 써야 할 건 없는 것 같다. 처음 시작층과 0을 큐에 집어넣고 큐가 빌 때..