유형: dp 문제 리스트: https://solved.ac/search?query=돌 게임 solved.ac - 검색 solved.ac 돌 게임 문제는 조금씩 변형해서 여러 문제가 있다. 1, 3개씩 가져가는 경우, 4개씩도 가져가는 경우, 마지막으로 가져간 사람의 승패를 반대로 하는 경우가 주로 있다. 문제 자체도 다소 추상적이라 감을 잡기 쉽지 않지만, 이런 문제는 규칙만 알면 O(1)로도 풀 수 있다. 몇달 전에 풀긴 했지만, 나는 1, 3개씩 가져가는 경우에서 규칙을 찾았었다. 개수를 2로 만들면 1밖에 못가져가기에 무조건 2로 만든 사람이 이긴다. 이걸 활용했던 것 같다. 패턴을 파악하기 위해 1부터 시작해서 경우의 수를 그려나갔다. 6~7정도가 되면 패턴이 보인다. 1, 3, 4개씩 가져가는 ..
유형: 그래프, BFS 문제 Small: https://www.acmicpc.net/problem/16173 문제 Large: https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 입출력 형식 main에서 입력을 받아오고, solution 함수에서 계산함. 이후 풀이는 solution 부분 코드만 올림. #include "iostream" #include "vector" #include "queue" using namespace std; string s..
유형: 그리디 문제: https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 풀이 첫 번째 나무는 1일차에 심는다. 그리고 0부터 시작한다. [2, 3, 4, 3]의 경우, 2일 걸리는 나무를 첫 번째로 심는다 치면, 1일차에 0부터 시작, 3일차에 2가 된다. 그러니 각 나무가 다 자라는데 걸리는 시간은, 각 배열의 원소값 + (인덱스 + 1) 이다. 1일차부터 시작한다는 것은, 배열 순서를 세는 기준을 1로 잡는것과 동일..
유형: dp 문제: https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 입출력 형식 계산할 값이 들어오면 solution 함수에서 계산한다. 풀이는 solution 함수만 올림. #include "iostream" #include "vector" using namespace std; int solution(int n){ // ... return 0; } int main(){ int total; cin >> total; cout
유형: 그래프, 완탐 문제: https://www.acmicpc.net/problem/14397 14397번: 해변 단위 정육각형 이루어져 있는 지도가 주어졌을 때, 해변의 길이를 구하는 프로그램을 작성하시오. 해변은 정육각형의 변 중에서 한 쪽은 물인데, 한 쪽은 땅인 곳을 의미한다. www.acmicpc.net 풀이 문제에 주어진 문자열을 물이면 1, 땅이면 0인 2차원 벡터로 변환했다. 육각형 형태라, 한 노드의 주변 노드까지 합치면 꽃모양이 된다. (주변 노드는 최대 6개이기에) 2차원 벡터의 모든 노드를 탐색하면서, 땅일 경우에만 주변 노드중 바다인 것만 세주면 된다. 주의할 점은, 노드가 세로 몇째 줄이냐에 따라 주변 노드가 달라진다는거다. 그렇기에 짝수번째, 홀수번째 노드의 주변 노드 위치를..
