![]()
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 에 따라 몇 가지 경우의 수가 있습니다. ..
![]()
1. 백준 14289번 - 본대 산책 3 (Gold 1 - 분할 정복 기법을 사용한 행렬 거듭제곱 dp 문제) 더보기 https://www.acmicpc.net/problem/14289 14289번: 본대 산책 3 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 결국 정보대에서 정보대까지 d번만에 가는 경우의 수를 구해야 하는 문제였다. 이를 일반화 해보면 "A 노드에서 B 노드까지 d번만에 가는 경우의 수"를 구해야 한다. 이 부분을 dp스럽게 생각해보면 "A노드에서 B와 연결된 모든 노드까지 d-1번 만에 도착하는 경우의 수들의 합"과 같다. 즉 식으로 나타내면 다음과 같다. dp[i][j][k] = i 노드에서 j 노드까지 k번 만에 도착하는..
![]()
1. 백준 1086 박성원 (Platinum V - bitmask dp 문제) 더보기 https://www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 문제 N개의 수로 이루어진 집합이 주어진다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있는데, 합친 수가 정수 K로 나누어 떨어지는 순열의 개수를 구하는 문제이다. * 테스트 케이스 설명 집합 {3, 2, 1} 이 주어졌는데, 이 집합으로 만들 수 있는 순열은 다음과 같이 6가지 되시겠다. {1, 2, 3}, {1, 3, 2}, {2, 1, 3..
![]()
www.acmicpc.net/group/practice/9883/20 어려운 문제는 D번, E번 문제라고 생각합니다. D번은 다른 분이 삼성 기출 문제 대비로 만든 문제로 3월 27일 모의테스트에서 진행했었던 문제이고, E번은 옛날 삼성 역량테스트 기출 문제입니다. 1. BOJ 9971 The Hardest Problem Ever www.acmicpc.net/problem/9971 9971번: The Hardest Problem Ever Julius Caesar lived in a time of danger and intrigue. The hardest situation Caesar ever faced was keeping himself alive. In order for him to survive, h..
![]()
www.acmicpc.net/group/practice/9883/18 2차원 리스트가 중요해서 2차원 리스트 3문제를 추가하였습니다. 문제는 6번이 제일 어려웠을 것이라고 생각합니다. 1. BOJ 12778 CTP 공국으로 이민 가자 www.acmicpc.net/problem/12778 12778번: CTP공국으로 이민 가자 신생국가 CTP공국은 자신들만의 글자가 없다. CTP공국의 왕 준형이는 전 세계 표준 언어인 알파벳을 사용하기로 했다. 하지만 숫자에 미친 사람들이 모인 CTP공국 주민들은 알파벳을 사용할 때 평 www.acmicpc.net 문제를 읽어보니 1을 입력 받으면 A를 출력하고, A를 입력 받으면 1을 출력하는 아스키 코드 변환 문제입니다. 1을 입력 받아서 A를 출력하려면 chr(1 +..
![]()
푸시느라 고생하셨습니다~ 문제 구성 백준 17141번 연구소 2 백준 2602번 돌다리 건너기 백준 2437번 저울 이번 문제 셋은 어느덧 정신 차려보니 벌써 한 학기가 절반이나 지났길래 부랴부랴 난이도를 높여보았습니다. 그래 봤자 랑이 집사님은 19분 컷 하셨네요 😅🤣 1. 백준 17141번 연구소 2 bfs + 브루트 포스 (백트래킹) 문제입니다! 단순히 바이러스가 퍼지는 시간을 구하는 것은 생략하고, 백트래킹 시간 복잡도만 설명하고 넘어갈게요! 문제 입력에서 놓을 수 있는 바이러스의 개수 M의 범위는 최대 10입니다. 그리고, 바이러스를 놓을 수 있는 칸인 2의 개수는 M 이상, 10 이하라고 합니다. 따라서 바이러스를 놓는 경우의 수는 바이러스를 놓는 칸 중 M개를 뽑는 경우가 되겠네요 이 두 수..
![]()
www.acmicpc.net/group/practice/9883/17 이번 문제는 3번 문제가 문제 해석이 좀 힘들었겠고, 난이도는 5번이 제일 어려웠을 것으로 생각합니다. 1. BOJ 10769 행복한지 슬픈지 www.acmicpc.net/problem/10769 10769번: 행복한지 슬픈지 승엽이는 자신의 감정을 표현하기 위해서 종종 문자 메시지에 이모티콘을 넣어 보내곤 한다. 승엽이가 보내는 이모티콘은 세 개의 문자가 붙어있는 구조로 이루어져 있으며, 행복한 얼굴을 나 www.acmicpc.net :-), :-( 이모티콘 개수에 따라 출력 내용이 달라지는 문제입니다. 이모티콘의 길이가 둘 다 3이므로 for문을 (문장의 길이)-2번만 확인하면 되는 간단한 문제입니다. x는 :-)의 개수, y는 :..
