점프 점프 1*n 크기의 배열 점프는 i번째 칸의 숫자 이하의 횟수만큼 점프 가능 동전 줍기 문제랑 비슷 -> dp? dp로 각 i번째까지 갈 수 있는 방법 중 최소 점프 횟수 확인 #include #include using namespace std; int main(){ int n; cin>> n; int arr[1002], dp[1002]; for(int i=0; i> arr[i]; dp[i] = 100000; } dp[0] = 0; for(int i = 0; i dp[i] + 1){ //다음 자리의 결과 보다 크다 dp[i+j] = d..
Koala - 4기
생각 정리 1. 4개의 모서리에 최소 하나의 1이 존재 -> 4개의 모서리를 확인 후 1인 경우 건너뛰려고 했다. 2. 최대 넓이가 50x50이고, 회전 하지 않았을 때, 90도, 180도, 270도 총 4가지를 비교하면 50x50(A퍼즐)x50x50(B퍼즐)x4 = 25,000,000가지로 생각(하나의 퍼즐을 고정해야겠다는 생각을 하지 못했다.) 3. 두 개 퍼즐의 행과 열이 다른 경우에 맞춰주려고 함 -> 하나를 고정해야겠다는 생각을 못해서 n1 > n2이고, m1 m2인 경우 0을 채워서 행과 열을 같게 맞춰주려고 했다. 4. 0, 90, 180, 270도 회전을 했을 때 각각 생각 -> swap()을 생각하지 못하고 회전 경우마다 for문을 생성해서 각각을 고려해주려고 했다. 결론 : 중첩된 fo..
짠돌이 호석 1번째 퍼즐 N1 * M1 2번째 퍼즐 N2 * M2 액자 가격 = 행의 개수 * 열의 개수 90도 180도 270도 회전 가능 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 큰 퍼즐을 가운데에 기준으로 잡고 사방으로 돌려가면서 붙여보기 1. 큰 퍼즐 / 작은 퍼즐 구분 --> 이 방법은 어차피 어떤 퍼즐을 기준으로 잡고 놓아도 똑같은 방식이기 때문에 첫번째 퍼즐을 기준으로 잡았다 모든 방법 다 해봐야함 0 90 180 270 4가지 방안 확인해야함 비교해볼 때 시작할 위치를 정하는 방법이 2가지 존재 0,0 부터 100,100 까지 다 검색 하거나 or 크기에 맞춰서 a*b 크기면 50-a, 50-b 에서 부터 시작하는 방식이 있다. 그러나 후자의 방법으로 할 시 복잡하거나 헷갈린다는 조언을 듣고 전자 ..
# 여러줄에 많이 입력받으므로 input 대신 readline이 좋을 것 # 1번째 퍼즐이 변의 길이 x1 y1이고 2번째 퍼즐의 변의 길이 x2 y2라고 할때 # 최대 넓이는 (x1+x2)*max(y1,y2) 와 (y1+y2)*max(x1,x2) 중 큰 값일 것? # 혹시 모르니 마지막에 min으로 테스트 해봐도 좋을 듯 # 4개의 모서리에는 꼭짓점이 존재, 두 조각 모두 한변의 길이도 3보다 작은 경우 # 무조건 2*2 1*1 => 6칸 or 8칸 or 2칸 # 아닌 경우 꼭짓점이 아닌 부분에 하나하나 넣어 보면 될듯? # (0,0),(0,m1),(n1,0),(n1,m1)가 아닌~ # 두 퍼즐 모두 회전시킬 필요는 없을 것 하나만 회전시키고 (*3) # 남은 퍼즐 하나를 일일히 넣어보는 것 # 다 돌..
#https://www.acmicpc.net/problem/12906 #1 '최소'로 움직이려면? # 모든 경우 다 돌아보려면? # 한 막대에서 옮길수 있는 선택지 2개 # 막대 개수 3개 # 6**10? # 풀이? #1) # bfs로 돌리다 맨 처음에 입력받은 A개수 B개수 C개수와 # 1,2,3 막대에 들어있는 것들의 개수가 모두 같으면 이게 답인지 확인 # bfs로 하면 확정적으로 정답(최소)을 구할 수 있을 것 (아마도), #1-1) # # bfs 결과 다 담아놓고 정렬 # 막대에는 빈 공간에 'AA' 이렇게 채워줘서 정렬시에 AAA BBB CCC 순서로 올 것. #2) # 가장 효율적인 방법? # 바닥부터 완성시키는 것, 1번 막대 맨 밑에 있는 연속된 a는 움직일 필요가 없음 #2-1) # 한..
힌트 1 더보기 입력 제한이 아주 작습니다! 힌트 2 더보기 둘 중 더 큰 퍼즐 A를 고정시켰다고 가정할 때, 답이 될 수 있는 퍼즐 B의 위치가 얼마나 있는지 잘 생각해보세요. 풀이 더보기 편의상 두 퍼즐을 A, B라 하겠습니다. 만약 어떤 퍼즐 A를 고정시켜두었다면, 답이 될 수 있는 퍼즐 B의 위치는 다음과 같습니다. 직접 작업을 하다보니 그림 상태는 양해 부탁드립니다 😅 그림을 통해 말하고 싶은 점은, B의 위치가 될 수 있는 가짓수가 얼마 없다는 점입니다. B의 위치가 A 넓이를 벗어나게 되면, 전체 정답은 A에 붙어있느니만 못하기 때문에, 딱 위 그림 영역 정도가 답이 되겠죠. 따라서 저 영역의 범위를 수식으로 계산해봅시다. 문제처럼 A의 행, 열이 (n1, m1) B의 행, 열이 (n2, m..
https://www.notion.so/Koala-4-orientation-e3d42176382346489b3ef41e7bb725ea
