작심 24/7

1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 수학적으로 풀어도 되지만 백트래킹으로 풀어보았다. 계산에 사용되는 M개의 알파벳을 모아놓고 9부터 M개의 숫자를 순열로 대입하였다. ex) ADC -> 3개의 숫자 9, 8, 7을 순열로 배치시키면 알파벳 ADC는 987, 978, 897, 879, 798, 789 이렇게 숫자가 대입될 수 있다. map을 이용해서 각 알파벳에 숫자를 대입해주고 배치가 완료되면 단어의 합을 계산해주고 최댓값을 갱신한다. 이때 stoi를 이용하여 계산을 했었는데 시간 초과 나..

17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 궁수 3명을 배치시키는 경우는 M개 중 3개를 순서 상관없이 뽑는 조합으로 구하면 된다. 궁수가 (5, 2)에 있을 때 공격할 수 있는 위치에 따른 거리들을 표시해 보았다. 궁수가 공격할 수 있는 거리는 궁수 위치에서부터 좌, 상, 우 방향으로 BFS 했을 때의 깊이와 같다는 것을 알 수 있다. 공격할 수 있는 적은 거리가 D 이하인 적 중에서 가장 가까운 적이고 그런 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격해야 하므로 깊이 1부터 탐색해야 하고 방향은 왼쪽, 위쪽..

16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 1. 괄호로 묶지 않는 경우 이전까지의 값 OP 숫자 = res a[idx] a[idx+1] 2. 괄호로 묶는 경우 이전까지의 값 OP (숫자 OP 숫자) = res a[idx] (a[idx+1] a[idx+2] a[idx+3]) 재귀 호출을 이용해 수식의 처음부터 끝까지 돌면서 1번 경우는 무조건 계산하고 2번 경우는 뒤에 남은 수식이 괄호를 추가할 수 있을 만큼 남아있는 경우에만 계산한다. #include #include #include #in..

17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 주사위를 던질 때마다 선택할 수 있는 말은 4가지이고 주사위는 10번 던지므로 말을 이동하는 총 경우의 수는 4^10가지가 된다. (중복 순열) 게임판에서 말이 어떤 파란색 칸으로 이동하는지에 따라 경로가 달라진다. 1. 파란색 칸을 한 번도 밟지 않는 경우 (Default) 2. 1번 경로로 가다가 첫 번째 파란색 칸을 밟는 경우 3. 1번 경로로 가다가 두 번째 파란색 칸을 밟는 경우 4. 1번 경로로 가다가 세 번째 파란색 칸을 밟는 경우 이 네 가지 경우에 따른 경로를 이차원 배열 board에 저장해준다. 말을 이동시킬 때 같은 칸에 두 개 이상의 말이 있으면 안 되므로 A 말을 이..

2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 9명 중에 순서 상관없고 중복 없이 7명을 찾아내는 것이므로 조합이다. 조합 함수를 만들어서 재귀로 풀어주면 된다. 결과 벡터에 있는 값 < 현재 배열에 있는 값인 경우에만 push와 카운트, sum에 더해주고 재귀호출 해주며 카운트가 7이 될 때까지 반복한다. 카운트가 7이고 sum이 100이면 출려해주고 끝내고 아닐 경우엔 돌아와서 pop, 카운트와 sum에서도 빼준 뒤 다음 배열의 값으로 넘어간다. #include #include #include using name..

14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 조합 문제의 변형이다. N에 따라 나눌 수 있는 팀의 경우의 수를 살펴보면 N 팀 2 1 | 2 ==================== 4 1, 2 | 3, 4 1, 3 | 2, 4 1, 4 | 2, 3 ==================== 6 1, 2, 3 | 4, 5, 6 1, 2, 4 | 3, 5, 6 1, 2, 5 | 3, 4, 6 1, 2, 6 | 3, 4, 5 1, 3, 4 | 2, 5, 6 1, 3, 5 | 2, 4, 6 1, 3, 6 | 2, 4, 5 1, 4, 5 | 2..

14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 순열 문제의 변형이다. 연산자 배열을 만들어 나열시켜주고 순열 알고리즘 처럼 check 배열을 만들어 갔다 온 곳은 체크 해준다. 재귀를 이용해서 끝까지 계산 해주고 완료되면 최댓값 최솟값 비교를 해준다. 재귀가 끝나고 돌아오면 값을 이전 값으로 다시 만들어주며 반복한다. #include #include using namespace std; int Max = -1111111111, M..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹으로 푸는 문제이다. 1. 같은 행에 숫자 N이 없을 때 2. 같은 열에 숫자 N이 없을 때 3. 같은 3*3 칸에 숫자 N이 없을 때 이 세 조건을 충족시키면 다음 빈칸을 채우러 가고 만족시키지 못한다면 N+1을 하여 다음 숫자를 넣어본다. N을 9까지 증가시켰는데 빈칸을 채우는데 실패하면 이전 빈칸의 숫자가 잘못된 것이므로 돌아간다. 모든 빈칸이 채워지는 경우엔 finish에 표시한 후 모두 빠져나와 출력시키면 끝 #include #include us..