공부혜옹

돌 게임 6 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 2231 1135 1048 52.849% 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 돌게임3의 타입만 바꿔주니 당연히 메모리 초과가 났다. 따라서 새로운 방법을 찾아보았다...

돌 게임 5 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 2820 1780 1645 68.915% 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 돌게임1과 같은 문제이나 n의 범위가 엄청나게 늘어났다. 따라서 int형이었던 n의 타입을 lo..

돌 게임 4 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 3029 1403 1253 48.831% 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 지게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 돌게임3에서 분기문 조건만 반대로 바꿔주면 될거라고 생각해서 엄청 많이 틀린문제..정말 바보였다 ㅎㅎ,,, 상근이..

돌 게임 3 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 4238 1949 1634 48.689% 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 마지막에 남은 돌갯수 1 2 3 4 5 6 7 8 9 상근 시작 이김 짐 이김 이김 이김 창영 시작 이김 짐 이..

2021.05.11 - [공부합시다/Algorithm] - 백준 9655번 돌게임 이전에 풀었던 돌게임에서 마지막에 고르는 사람의 승패조건만 바뀌는 문제이다. 따라서 n이 짝수일때 상근이가 이기는 코드로 바꿔주면된다. 뭔가 멋있는 풀이법이 있는걸까.. 같은문제 같은데 왜 1은 실버5고 2는 실버4인걸까 백준 9655번 돌게임 돌 게임 1 초 128 MB 8616 5617 4911 66.545% 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져 hae-ong.tistory.com #include using namespace std; int main() { int n; cin >> n; if(n%2 ..

돌 게임 1 초 128 MB 8616 5617 4911 66.545% 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 두명이서 게임하면서 가져가는 경우의 수가 홀수개이다 (1개, 3개) 따라서 총 돌의 수가 짝수이면 늦게 고르는 창영이가 홀수이면 상근이가 이긴다. #include usi..

구간합을 구하는 문제와 비슷한 로직으로 트리에 합이아닌 최솟값을 넣어주고, 업데이트를 할 필요가 없다는 점이 다르다. 자식노드들이 범위에 벗어나느경우와 벗어나지않고 포함되는 경우 혹은 걸쳐 있는 경우등을 따져 최솟값을 구해준다. #include #include #include #include #define INF 987987654321 using namespace std; typedef long long ll; ll make_Tree(vector &a, vector &tree, int node, int start, int end) { if (start == end) return tree[node] = a[start]; int mid = (start + end) >> 1; return tree[node] ..

update는 target 위치에 value값을 업데이트 해주고, 트리에서 a[idx-1]과 같은 값은 가지는 노드의 부모노드를 타고 올라가며 업데이트 해준다. 이때 범위가 벗어나는 경우 부모 노드가 양쪽 두 자식 값을 통해 곱을 재 연산하기 위해서 return A[index]를 해준다. 합처럼 일부만 갱신하는게 아닌, 해당 가지부분을 전체 갱신하여 재연산해주어야 된다. #include using namespace std; const int MOD = 1000000007; int n, m, k; long long A[4000000]; long long update(int index, int target, int value, int start, int end) { if (start > target || e..