![]()
1~1000 사이의 n입력받아 길이가 n인 배열을 입력받는다. 한 번에 이동할 수 있는 거리는 0~100 사이의 값이고 1부터 1000까지 최대 이동 횟수는 999회. 각 위치에 해당하는 최소 이동횟수를 저장시켜야 함 -> DP 문제일 것. 입력도 작고 이동 거리도 작으므로 그냥 BFS로 다 넣어서 풀어도 풀리긴 할 것? bfs 풀이 쓸데없는 곳까지 굳이 탐색하여 시간효율도 별로고 배열도 써서 메모리 효율도 별로일 듯.. dp로 예상됨. # 뒤로 가는거 없음. # bfs? 로 풀 수 있을 듯? import sys from collections import deque input=sys.stdin.readline n=int(input()) arr=list(map(int,input().split())) vis..
생각 정리 1. dp[i]를 점프해야 하는 최소 횟수로 정의 2. 횟수가 제일 많은 경우는 n이 1000이고, 입력된 숫자가 모두 1일 때라고 생각(-1이 나오지 않는 범위에서) -> 시간 초과가 나지 않는다고 생각. 3. 점프해야 하는 최소 횟수를 정의하라고 했기 때문에 dp의 모든 인덱스를 아주 큰 수로 초기화 4. a[i]에 입력된 수만큼 떨어진 곳 이하에 점프해야 하는 최소 횟수를 대입하고, 미리 저장되어 있는 최소 횟수와 그 이후 들어온 횟수를 비교해서 min 값을 저장 5. dp[n]이 987654321로 남아있다면 도달하지 못한 것이므로 -1을 출력 소스코드 #include #include #include #define MAXNUM 987654321 using namespace std; in..
![]()
문제 링크 : https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net DP 문제입니다. 저는 원체 DP에 익숙하질 않아 상태표를 그려가면서 규칙을 파악하려 했는데요, 그 결과 다음과 같은 흐름을 잡을 수 있었습니다. 10 1 2 0 1 3 2 1 5 4 2 위의 기본 테스트케이스를 예로 들어 설명해보겠습니다. 입력받은 값들이 arr 라는 배열에 담겼다 하고, 해당 배열의 순회를 시작합니다. (1번 for문) 조건에 따르면 배열의 요소에 해당..
점프 점프 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..
생각 정리 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
![]()
A. Exciting Bets 문제 설명 + 풀이 a, b가 주어집니다. 이때 움직임 : (a, b를 1 증가 or a, b가 0이 아니면 1을 감소)해서 gcd(a, b)의 최대값과 gcd(a, b)를 만들 수 있는 최소의 움직임 횟수를 출력하시오. 만약 gcd(a, b)가 무한대라면 0 0을 출력 1. a == b라면 0 0을 출력 (gcd(a, b)가 무한대 일 때) 2. gcd(a, b)의 최대는 (a > b)일때 a - b가 최대가 된다. 3. 최소 움직임 : (a > b)일 때 b % (a - b)가 (a - b) / 2보다 작거나 같다면 움직임의 최소는 b % (a - b)이고, 크다면 (a - b) - b % (a - b)가 된다. 소스 코드(. cpp) #define _CRT_SECURE..
1. SCPC 2018 1차 예선 2 - 회문인 수의 합 더보기 풀이 처음에 알고리즘 분류를 DP로 알고 있어서 DP로 생각하다가 우주 갔다가 돌아온 문제이다. 이 문제는 브루트포스로 해결이 가능했다. 브루트포스에서 가장 중요한 점인 시간 복잡도만 체크해보자. (아이디어는 떠올리기 어렵지 않다) 먼저 n제한은 10000이고 시간 제한은 1초이다. 즉 O(n제곱)은 성립하지 않는다. 그렇다면 이곳저곳에서 컷팅을 시도해보자. 먼저 우리가 체크해야 할 것은 총 3가지 이다. 1. 자기 자신이 바로 회문인 경우 2. 2개의 회문의 합으로 이루어진 경우 3. 3개의 회문의 합으로 이루어진 경우 자기 자신이 회문인 경우는 1~10000까지 각각 체크해주면 되므로 O(1만)이다. 2번째 경우 역시 마찬가지로 1~10..
