약간 어려움 (3) 썸네일형 리스트형 [BOJ 27296, 약간 어려움] 카탈란 마스터의 선분 그리기 게임 (C++) 개인적인 난이도 약간 어려움 문제가 정말 안 읽힌다. 카탈란이 뭔지도 모르겠고 처음엔 이게 무슨 어려운 정수론 문제인 줄 알았으나 한참 생각하고나서야 애드혹인걸 알았다 게임 이론 문제에 ->>> 두 명의 플레이어가 모두 자신이 승리하기 위해 최선으로 행동한다면이라는 내용이 들어가면, 상상도 못한 쉬운 답이 나오는 경우가 많은 것 같다. 과거에도 https://www.acmicpc.net/problem/26074 이거 풀면서 그렇게 생각했다. 접근 방법) 점의 개수가 N이라는 정수로 주어졌을 때, N이 커지면서 그릴 수 있는 다각형의 개수는 수없이 많아진다. 그렇지만 이 문제의 조건은 N이 정해졌을 때 선공이 이긴다 또는 후공이 이긴다 의 결과가 딱 1가지만 존재함을 내포하고 있다. 그러므로 우리는 점의 .. [BOJ 1799, 약간 어려움] 비숍 (C++) 개인적인 난이도 약간 어려움 실패한 풀이) 체스판에서 대각선을 체크하면서 말을 놓는 백트래킹의 구현은 그렇게 어렵지 않으나, 그냥 백트래킹하면 시간초과가 나게 되는 문제이다. 약간의 아이디어로 시간복잡도를 크게 줄일 수 있다. 안되는 이유 최악의 경우, 10*10 의 배열의 모든 칸에 비숍을 배치할 수 있다 검사할 칸의 개수 100개 -> 백트래킹 없이 완전탐색할 경우 2^100~=1e30 대략 1e22초 소요 백트래킹으로 탐색하며 비숍을 배치할 수 있는 위치에만 비숍을 배치한다고 해도 시간초과가 난다. 그 이유는 이러하다. 10*10 크기의 2차원 배열의 경우 20+20 개의 대각선을 그릴 수 있다. 인정?? 인정~ 비숍을 어느 한 위치에 놓을때마다 우상향 방향 대각선 1개와 좌상향 방향 대각선 1개에.. [BOJ 27231, 약간 어려움] 2023년이 기대되는 이유 (C++) 개인적인 난이도 약간 어려움 정석 풀이는 아마 백트래킹으로 문자열 중간에 +를 삽입하는 것이다 근데그냥 브루트포스로 풀어도 풀린다 난 백트래킹 말고 그냥 set 반환하는 재귀함수 만들어서 브루트포스로 풀었다 재귀는 항상 어렵다 dp문제를 풀때도 항상 느끼지만 어떤 연산을 절차적으로 생각하는 건 익숙하지가 않다 그래서 한참 걸려서 풀었다 1시간정도걸림 수련이 부족하다 성공한 풀이) 성공한 코드 #include #define fastio cin.tie(0)->sync_with_stdio(0) #define ll long long using namespace std; ll pow(int a,int b){ if(a==0)return 0; if(a==1)return 1; if(b==0)return 1; retur.. 이전 1 다음
