문제:https://www.acmicpc.net/problem/12851난이도: 골드 4숨바꼭질(실버 1)의 확장판. 숨바꼭질 같은 경우는 visited를 0과 1로 체크해 주면서 이동하면 bfs로 해결할 수 있었지만, 최단 경로의 개수를 구해야 하므로 단순히 0과 1로만 체크를 하면 안 된다는 걸 알 수 있다. 아이디어 1처음에는 단순 bfs를 변형해서 풀 생각을 했다. 최솟값을 찾으면 그걸 저장해 주고 개수를 세주다가 더 작은 최솟값이 나오면 갱신해서 다시 세주는 방식으로 끝까지 세어줬다. 시도 1from collections import dequen,k = map(int,input().split())c=[0]*100001d=deque()d.append(n)c[n]=1s=0check=Truemin_s..

문제:https://www.acmicpc.net/problem/12865정석적인 dp 문제이나... 이해하는데 꽤나 애를 먹었다. 다음 문제를 위해 정리해서 글을 끄적여본다.아이디어1우선 처음에는 이중 for문을 돌면서 리스트에다가 가능한 모든 조합을 넣어서 max 값을 뽑아냈다.(난 이게 완전 탐색인지도 몰랐다) 시도1from collections import dequen,k=map(int,input().split())w=[0]*nv=[0]*nfor i in range(n): w[i],v[i] = map(int,input().split())d=deque()c=0for i in range(n): d.append((w[i],v[i])) for j in range(0,len(d)-1): ..

오늘 공부한 내용 & 푼 주요 문제9657 - 돌 게임 3(실버 3)https://www.acmicpc.net/problem/96579659 - 돌 게임 5(실버 3)https://www.acmicpc.net/problem/96599660 - 돌 게임 6(골드 5)https://www.acmicpc.net/problem/96609661 - 돌 게임 7(골드 2)돌 게임 시리즈를 풀어봤다. 전반적으로 dp에 대한 기본적인 이해를 요구했고, 9660,9661은 이를 토대로 일반항을 세워 O(1)의 시간복잡도를 요구하는 문제였다. 돌 게임 시리즈의 마지막 문제인 돌 게임 8은 이를 더 일반화 하는 내용인데, 이에 대한건 조금 더 공부를 하고 풀어봐야겠다. 1439 - 뒤집기(실버 5)https://www.ac..

다음 달에 우리 학교에서 코딩 대회가 열린다. 여차여차해서 내가 출제자로 뽑히긴 하였으나... 출제자라 부르기엔 너무 실력이 부족하다. 또한 출제자 요건 중 하나가 바로 백준 1000문제 이다. 따라서 오늘부터(7.7) 1000문제 도전기를 시작한다. 목표우선 내 목표는 다음과 같다.1000문제 달성플레 5 달성클래스 6 달성계획하루마다 오늘 푼 문제와 공부한 내용을 정리해서 올릴 것이다. 그 중 실버 이상의 문제는 따로 간단한 주석을 달아둘거고, 그 중 골드 이상의 문제는 따로 문제풀이 글을 남길것이다.우선 목표는 하루에 20~30문제씩 푸는 것이다. 그럼 어림잡아 1000문제 푸는데 25일 정도가 걸릴 것이고, 대회 일자랑 비슷하게 맞출 수 있다. 여기서 5문제 정도는 실버 이상으로 맞춰서 플레5를 ..

문제:https://www.acmicpc.net/problem/9663 n*n 격자판 위에 n개의 퀸을 배치할때, 퀸이 서로를 공격하지 못하게 배치하는 경우의 수를 구하시오.백트래킹을 이용하는 굉장히 유명한 문제이다.아이디어백트래킹을 이용해서 위쪽 줄부터 차례대로 재귀함수를 사용해 탐색하면서 내려가면 된다.이때 겹치는 세로줄,대각선을 체크하여 들어갈 수 있는지 확인하기 위한 리스트를 만든다. 우하향,우상향 대각선을 분리해서 생각해주었다. 퀸이 있는 자리에 배열 값을 바꿔주면서 내려와서 마지막줄에 도달하면, count +=1을 해주어 개수를 세었다.각 x,y에서 col1,diag1,diag2의 어떤 값이 올지 생각해주는게 관건이었던거 같다.정답 코드n=int(input())col1=[0]*n#세로diag1..

문제:https://www.acmicpc.net/problem/1074 1인 경우, 배열을" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/1074" data-og-url="https://www.acmicpc.net/problem/1074" data-og-image="https://scrap.kakaocdn.net/dn/tjWnJ/hyTBHl0I87/73TRFfjERJ85Pv9iBfzzCK/img.png?width=2834&height=1480&face=0_0_2834_1480,https://scrap.kakaocdn.net/dn/buCrT6/hyTBDjCCnG/dr3twovjDIx5zTxPwgXnH1/..