컴굥일지

문제 https://www.acmicpc.net/problem/2011 문제 내용 A~Z까지의 알파벳을 1~26으로 각각 매칭 해두고 암호화를 진행했다. 숫자로 이루어진 암호가 주어질 때, 이를 해석하고자 한다. 해석할 수 있는 가짓수를 출력하면 된다. (정답이 매우 클 수 있으므로, 1,000,000으로 나눈 나머지를 출력한다.) 문제 풀이 dp문제이다. 일단 가장 첫 숫자가 0이라면 암호 자체가 잘못되었기 때문에 0을 반환한다. dp[a]=b라고 쓰면 a번째까지 해석할 수 있는 가짓수가 b 개라는 뜻이다. dp[1]=1이다. 왜냐하면, 1번째 숫자까지 읽을 수 있는 단어의 개수는 1개이기 때문이다. (1이라면 A, 2라면 B... 9라면 I가 된다.) 그럼 dp[2]는 얼마일까? 이때부터는 고려사항이..

문제 https://www.acmicpc.net/problem/2580 문제 내용 완성되지 않은 9*9 크기의 스도쿠를 입력받아 완성시키는 문제이다. 문제 풀이 이 문제는 백트래킹 방식을 통해 문제를 풀었다. 아직 채우지 못한 빈칸을 찾아서 배열에 저장한 뒤, 그 빈칸에 1~9를 차례로 넣어보며 스도쿠를 완성시키는 방식으로 문제를 해결하면 된다. 스도쿠의 특성상, 같은 행 / 같은 열 / 같은 3*3칸 안에서는 1~9이 숫자가 한 번씩만 나올 수 있다. 이 특성을 체크하기 위해 check() 함수를 별도로 만들어 사용했다. 코드 #include #include #include using namespace std; vectorblank; bool finish = false; //1~9 체크 bool che..

문제 https://www.acmicpc.net/problem/9657 문제 내용 상근이와 창영이가 번갈아가며 돌을 가져가는데, 한 번에 1개, 3개, 4개를 가져갈 수 있다. 마지막 돌을 가져가는 사람이 이기는 게임이다. 누가 이기는지 구하면 된다. 문제 풀이 [백준 9655 돌 게임] 문제에서 가져갈 수 있는 돌의 개수가 하나 더 추가된 문제이다. 돌의 개수에 따른 규칙은 밑의 코드 주석으로 달아두었다. 코드 #include using namespace std; int dp[1005] = { 0, }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int n; cin >> n; //문제 해결 /* 마지막에 가져가는 사..

문제 https://www.acmicpc.net/problem/9655 문제 내용 상근이와 창영이가 번갈아가며 돌을 가져가는데, 한 번에 1개 또는 3개를 가져갈 수 있다. 마지막 돌을 가져가는 사람이 이기는 게임이다. 누가 이기는지 구하면 된다. 문제 풀이 규칙만 알면 매우 쉬운 문제이다. 돌의 개수에 따라 규칙을 찾아보자 n=1: 상근이가 먼저 가져가므로 상근이가 이긴다. n=2: 상근(1), 창영(1) 이므로 창영이가 이긴다. n=3: 상근(3) 이므로 상근이가 이긴다. n=4: 상근(3), 창영(1) 이므로 창영이가 이긴다. (1 3 또는 1 1 1 1 이어도 창영이가 이긴다.) n=5: 상근(3), 창영(1), 상근(1) 이므로 상근이가 이긴다. (1 3 1 또는 1 1 3 또는 1 1 1 1 ..

문제 https://www.acmicpc.net/problem/20301 문제 내용 1~N번까지의 사람이 원을 이루며 앉아있고, 계속해서 K번째 사람을 지워나가면 된다. 이때, M명의 사람이 제거될 때마다 방향을 바꿔나가면 된다. 문제에서는 사람을 지워나가는 순서를 출력하기를 바란다. 아래 링크는 백준 1158 요세푸스 문제이다. 이 문제에서 'M명의 사람이 제거될 때마다 방향을 바꾼다'라는 조건을 추가하면 지금 풀고자 하는 문제가 된다. https://gyong0117.tistory.com/entry/BOJ%EB%B0%B1%EC%A4%80-1158C-%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4-%EB%AC%B8%EC%A0%9C 문제 풀이 백준 1158 요세푸스 문제는 queue로 ..

문제 https://www.acmicpc.net/problem/18115 문제 내용 사용할 수 있는 기술 3가지가 있다. 1. 제일 위의 카드 1장을 바닥에 내려놓는다. 2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 이 기술들을 사용하여 카드를 다 내려놓았을 때, 카드의 순서가 위에서부터 순서대로 1,2,3,..., N이 되어있다. 초기 카드 상태를 구하는 문제이다. 문제 풀이 역순으로 계산해야 하기 때문에 조금 헷갈렸다. 초기 상태 : ????????? 기술 사용 순서: 2 3 3 2 1 (예시) 최종 상태 : 5 4 3 2 1 우리는 최종 상태와, 기술 사용 순서를 가지고 ..

문제 https://www.acmicpc.net/problem/14713 문제 내용 앵무새들의 말로 문장 L을 만들 수 있는지 없는지 판단하는 문제이다. 문제 풀이 앵무새가 말하는 데에는 규칙이 있다. 1. 한 앵무새는 한 문장을 기억하고 있다. 문장은 여러 단어로 이루어져 있는데, 앵무새는 이 단어들을 순서대로 말한다. 2. 한 앵무새가 단어를 말하고 그다음 단어를 말하기 전에는 약간의 간격이 있는데, 이때 다른 앵무새가 말을 가로채고 자신의 문장을 말할 수 있다. 3. 한 앵무새가 단어를 말하는 도중에는, 다른 앵무새가 말을 가로채지 않는다. 4. 어떤 단어도 앵무새가 말하는 모든 문장을 통틀어 2번 이상 등장하지 않는다. 위 규칙을 살펴보면, 1번과 2번 규칙을 통해서 문제 해결에 queue를 사용..

문제 https://www.acmicpc.net/problem/19941 문제 내용 햄버거 H와 사람 P의 순서가 표시된 문자열이 주어진다. 사람은 자기 주변으로 k만큼 거리 안에 있는 햄버거만 먹을 수 있다. 최대한 많은 사람이 햄버거를 먹을 수 있도록 할 때, 최대 사람 수를 구하면 된다. 문제 풀이 greedy한 문제이다. 사람을 기준으로 (-k~k) 범위 안에 있는 햄버거 중 가장 좌측에 있는 것을 먹도록 하면 된다. 햄버거를 먹으면 그 배열의 원소를 H나 P가 아닌 문자로 바꾸고 계속 탐색을 진행하면 된다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); ..

문제 https://www.acmicpc.net/problem/11501 문제 내용 날 별로 주식의 가격이 주어진다. 이때 우리는 주식을 사거나 / 팔거나 / 아무것도 안 하거나 3가지 중에 골라야 한다. 최대 이익을 만들어 결과를 출력하면 된다. 문제 풀이 문제를 읽고 나서 가장 먼저 떠오르는 것은 앞에서부터 차례로 확인해나가는 방법이었다. 현재 구입하는 시점 이후에 가장 비쌀 때 팔아버리면 된다. 현재 구입 시점이 가장 비싸다면 사지 않으면 된다. 다만, 이 방법은 구현하기가 어려웠다. 현재 구입하는 시점 이후 중, 가장 비싼 때를 찾기가 어렵기 때문이다. 그래서 뒤에서부터 확인하기로 했다. 그렇게 되면 가장 비쌀 때를 먼저 확인하고 이후에 주식을 살 수 있다. 코드 #include #include ..

문제 https://www.acmicpc.net/problem/13413 문제 내용 문자열 두 개를 입력받아서 한 문자열을 다른 문자열로 바꾸기 위해 몇 번의 연산이 필요한지 계산하면 된다. 이때 연산의 종류로는 2가지가 있다. 1. 배치된 말 중에 임의의 2개의 말을 골라 서로의 위치를 바꾼다 2. 말 1개를 들어 뒤집는다 문제 풀이 초기 상태와 목표 상태에서 서로 일치하지 않는 위치에서 w와 b의 개수를 구한다. (초기 상태 기준으로 구했다) 잘 생각해보면 따로 계산할 것이 없이 큰 값이 결괏값이 된다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); /..