반응형 알고리즘/BOJ21 BOJ 2428 ) 표절 (C++) 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net N이 10^6이므로 쌍을 찾기 위해 이중 for문을 돌릴 경우 시간초과가 난다. binary search를 써야하고 (i,j)와 (j,i)는 같은 케이스 이므로 i=0.9*v[n]; } int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin>>N; int t; for(int i=0;i>t; v.push_back(t); } sort(v... 2022. 6. 9. BOJ 2636 ) 치즈 (C++) 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 그림을 보고 문제에 접근하면 조금 더 발상이 쉽습니다. 그릇의 가장자리에는 치즈가 놓이지 않으며 치즈는 바깥에서부터 녹아 없어집니다. while문을 통해 판 위에 치즈가 없어질 때 까지(배열의 모든 원소가 0이 될 때 까지) 다음을 반복합니다. 가장 가장자리에서 BFS를 시작하고 치즈가 놓여있지 않은 좌표만 방문합니다. 다음 위치가 치즈인 경우 해당 원소의 값을 따로 변경해줍니다.(2로 변경) 치즈가 없어졌는지 확인하는 과정에서 2로 체크해준 치즈의 개수를 체크하고 원소가 2인 경.. 2022. 5. 9. BOJ 8983 ) 사냥꾼 (C++) 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net lower_bound를 이용해서 풀었다. lower_bound는 해당 범위에서 key값보다 같거나 큰 값 중 가장 작은 값을 반환한다. 사대를 입력받고 오름차순으로 정렬한 후 동물의 위치(a,b)를 입력받을 때 마다 해당 동물을 잡을 수 있는 사대 위치의 최솟값(a+b-L), 최댓값(L+a-b)을 구한 후 lower_bound를 이용해 사대 배열에서 min 값보다 같거나 큰 값 중 가장 작은 값의 위치를 구한다. 만약 그러한 값이 없다면 end를 반환하므로 조건.. 2022. 5. 1. BOJ 11652) 카드 (C++) 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 문제를 처음 봤을 때 바로 map이 떠올라서 map으로 풀었는데 정렬로 푸는 방법이 있다는 걸 알게 되서 정렬로도 풀어 보았다. # map 이용한 풀이 #include #include #include using namespace std; int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); int N; map m; cin>>N; while(N--){ long long s; cin>>s; if(m.find.. 2022. 3. 12. BOJ 12100) 2048(Easy) (C++) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net Easy라고 되어있는데 헤맸다. 구현 자체는 어렵지 않았는데 DFS처럼 구현을 해버리고 board는 원상복구를 안시켜줘서 자꾸 오답이 떴다. 매 회 보드의 형태를 기억할 순 없으니까 5번 돌리고 나면 다시 아예 처음으로 돌아가서 시행해줘야 한다. 큐를 이용해서 각 라인을 표현했다. 앞에 아무것도 없는 경우(temp = 0)에는 해당 값을 기억하고 큐에서 빼낸다. 앞에 블럭이 있는 경우 자신과 같으면 합쳐지면서 board에 덮어씌워지고 .. 2021. 10. 5. BOJ 18808) 스티커 붙이기 (C++) 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 구현 문제이다. 처음엔 돌리는걸 직접 구현하지 않고 노트북에 스티커를 붙여보는 단계에서 i, j를 조절해서 해결하려 하였으나 생각보다 신경쓸 부분이 많아서 스티커를 돌리는걸로 변경했다. 스티커를 돌리는 부분에서 i, j가 헷갈려서 또 한참 헤맸다. 각 스티커에 대해 붙일 수 있는지 검토한다(stick). 붙일 수 있는 공간이 있으면 붙이고 다음 스티커의 검토로 넘어가고 그렇지 않으면 스티커를 회전시켜 다시 시도한다. 스티커를 회전시킬 때 i, j가 어떤식으로 바뀌어.. 2021. 10. 4. 이전 1 2 3 4 다음 반응형
