# 여러줄에 많이 입력받으므로 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) # 남은 퍼즐 하나를 일일히 넣어보는 것 # 다 돌..
전체 글
항공대 알고리즘 동아리 Koala 🥰#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..
A. Odd Set 문제 설명 + 풀이 2n 개의 숫자가 주어진다. 이 수들 중 두 개씩 골라 n개의 페어를 만들고, 이 페어 안에 있는 두 수의 합이 모두 홀수가 될 수 있는지 확인하는 문제입니다. 간단합니다. 두 수의 합이 홀수가 되기 위해서는 반드시 홀수 + 짝수로 구성되어야 합니다. 따라서 2n개의 수들 중 n개가 홀수, n개가 짝수라면 yes, 아니면 모두 no입니다. 소스 코드(. cpp) #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; int ..
1. 백준 2159번 - 케익 배달 (Gold 2 - DP) 더보기 https://www.acmicpc.net/problem/2159 2159번: 케익 배달 첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다. (1 ≤ N, X, Y ≤ 100,000) www.acmicpc.net 풀이 문제의 핵심은 크게 2가지이다. 1. 주문이 들어온 순서대로 배달되기를 원함 2. 케익을 받는 고객의 위치까지 가거나 고객의 상하좌우 인접 격자점에 가야함 1번의 조건에 따라 i번째 최단 거리는 반드시 i-1번째 최단거리의 영향을 받는다. 따라서 앞서 구했던 최단거리들을 저장해놓고 사용한다 -> Dynamic P..
1. 백준 3687번 - 성냥개비 (Gold 2 - dp, Greedy) 더보기 https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 풀이 0~9까지의 숫자는 아래와 같은 개수의 성냥개비로 이루어진다. 0 = 6개, 1 = 2개, 2 = 5개, 3 = 5개, 4 = 4개, 5 = 5개, 6 = 6개, 7 = 3개, 8 = 7개, 9 = 6개 이 때 n개의 성냥개비로 만들 수 있는 최대의 숫자는 반드시 "1" 또는 "7"으로만 이루어진다. 왜냐하면 최대의 숫..
A. Pretty Permutations 문제 및 풀이 수열 [1, 2, ..., n] 을 i번째 인덱스의 수가 i가 되지 않도록 재배치합니다. 단, 숫자의 움직임(기존 i번째 수 -> j번 위치 이동 시 | i - j | ) 의 합을 가장 작게 하도록 재배치한 결과를 출력합니다. 처음에 [n, 1, 2, ..., n-1] 이 정답인 줄 알았는데, 한 번 틀리고 알았네요,, 만약 n이 짝수라면 모든 수는 1칸만 이동해도 재배치가 가능합니다. 배열에서 순서대로 2*i, 2*(i+1) 을 서로 뒤집어주면 됩니다. 반면 n이 홀수라면 딱 한 수만 2칸을 이동해주면 됩니다. 문제에서 나온 n=3 테스트케이스처럼, 맨 앞에 1,2,3 을 3,1,2 로 바꿔주면 이제 n-3은 짝수이므로 짝수일 때와 동일하게 둘 씩..
출처 : https://www.acmicpc.net/problem/20176 참고한 글 : https://koosaga.com/263 문제 및 풀이 3개의 선분이 위에서부터 차례대로 하나씩 있고, 각 선분 당 특정 좌표에는 구멍이 뚫려있습니다. 아래 그림은 정답이 될 수 있는 바늘이 3개의 선분을 통과한 사례입니다. 기본적으로 바늘이 3개의 선분을 지나가기 위해서는 a~b, b~c 를 지나갈 때 선분의 기울기가 같아야 하고, b의 위치가 동일해야 합니다. 즉, a+c = 2 * b 를 만족한다면 바늘은 선분을 지날 수 있습니다. (편의상, 배열 A, B, C 의 어떤 한 원소를 a, b, c 라 하겠습니다) 일반적으로 모든 a+c 를 구하기 위해선, 어쩔 수 없이 배열 A, C의 원소를 모두 순회하며 구..
A. Contest Start 문제 및 풀이 예외처리를 좀 해줘야하는.. 코드는 간단한 사칙연산 문제입니다. 그럼에도 불구하고.. 저도 끝까지 못맞추고, 1000점 tag가 달린 걸 보니 A번치고 어려운 문제라고 볼 수 있겠네요. 문제 요약을 하자면, n명의 사람이 있고 각 사람은 t 기간동안 대회에 참가합니다. 다만 각 사람이 대회를 시작하는 시점이 모두 다른데, 1 ~ n 명의 사람은 각각 x, 2x, ..., nx 에 대회를 시작하게 됩니다. 이 때, 어떤 사람 i가 대회가 끝났을 때 시점으로 대회를 진행중인 또는 대회를 지금 시작할 사람의 수를 "불만족" 이라고 합니다. 모든 참여자의 불만족 합을 구하는 문제입니다. 이 문제는 주어지는 변수 n, t, x 에 따라 몇 가지 경우의 수가 있습니다. ..