목록전체 글 (123)
풀이 보관함
🖍️ 풀이 주석 참고 💾 소스 #include #include // 길이 : A > B int solve(const std::vector& A, const std::vector& B) { int result = 0; // 마주보는 경우의 수만큼 이동한다. for(int i=0; i T; for(int test_case=1; test_case> N >> M; std::vector A(N), B(M); for(int i=0; i> A[i]; for(int i=0; i> B[i]; int answer = 0; if(N > M) answer = solve(A, B); else answer = solve(B, A); std::cout
🔗 문제 2865번: 나는 위대한 슈퍼스타K 2865번: 나는 위대한 슈퍼스타K 첫째 줄에 N, M, K가 주어진다. (1 ≤ M ≤ 100, 1 ≤ K ≤ N ≤ 100) 다음 M개의 줄은 각 장르에 대한 참가자의 능력이 주어진다. 이 줄에는 N개의 (i, s)쌍이 주어진다. 여기서 i는 참가자의 번호, s는 그 www.acmicpc.net +tmi 요즘 예~~전에 잘 못풀었던 문제들을 다시 보고 있다. 카카오 서버 다운된 이후로 티스토리를 접으려고 했는데 이 문제 쉽게 풀 수 있는데 유독 복잡한 풀이가 많은 것 같아서 올려봤다... 🖍 풀이 참가자는 여러 장르로 본선에 갈 수 없으므로 참가자의 가장 큰 점수만 저장하면 된다. 각 참가자의 최대 점수를 저장 내림차순 정렬 K명의 점수 합산 ✔️ 소수점 ..
🔗 문제 14891번: 톱니바퀴 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 🖍 풀이 더 효율적인 방법이 있나 검색해봤는데 나처럼 푼 사람은 없는 것같아 뿌듯.. (하지만 있을 수도.. ) 최대한 배열 복사하기가 싫어서 꼭지점 인덱스를 기준으로 풀었지만, 회전하고 나서 배열 변경해도 시간초과가 나지 않는다. deque를 이용해서 풀어도 시간초과는 나지 않는다. n번 톱니바퀴를 d방향으로 회전 시킨다. n번 톱니바퀴를 기준으로 왼쪽은 [n][6] 과 [n-1][2]의 값을 비교한다. n번 톱니바퀴를 기준으..
🔗 문제 14503번: 로봇 청소기 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 🖍 풀이 이 문제는 2차원 배열을 동서남북으로 이동하되 이동 방향 규칙에 유의해야 한다. 꼬박 하루나 붙잡은 문제다. 처음엔 후진을 2칸간다고 생각했기 때문이다…………………………………… 두번째엔 후진을 했을 때 방향을 유지하지 않고 왼쪽으로 돌려서 2번 예제도 나오지 않았었다. 🔄 방향 잡기 문제를 읽어보면 현재 방향(d)을 북동남서순으로 표현하고 있다. 그렇다면 왼쪽으로 d에 따라 좌회전을 하면 서북동남, 후진을 하면 남서북..
🔗 문제 1339번: 단어 수학 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 🖍 풀이 1) 수학적 접근 못 풀어서 이 분의 풀이를 참고했습니다. 설명도 정말 잘 되어 있으니 참고 바랍니다. 최고임. 🔗 https://mygumi.tistory.com/156 예를 들어 2개의 문자 ABC + BCD를 더한다고 생각해보자. ABC = 100A + 10B + C BCD = 100B + 10C + D ABC + BCD = 100A + 110B + 11C + D 이것을 내림차순으로 정렬한다면 어떻게 해야할지 ..
🔗 문제 9663번: N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🖍 풀이 먼저 백트래킹을 이용한 기초적인 문제로 백트래킹이 뭔지 알고 풀면 더 좋을 것 같다. 백트래킹이란? Promising을 통해 과정을 Prunning하는 기법 DFS(깊이 우선 탐색)과 비슷하지만 조건을 잘 활용하여 유망하지 않은 경로는 가지치기를 통해 진행하지 않는다. 이를 통해 메모리와 시간을 아낄 수 있다. N-Queen의 조건 퀸이 놓여진 수직, 수평에 다른 퀸을 놓을 수 없다. 퀸이 놓여진 대각선에 다른 퀸을 놓을 수 없다. ..
🔗 문제 2580번: 스도쿠 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 🖍 풀이 스도쿠 칸에 값을 넣는 조건 가로와 세로에 중복된 숫자가 올 수 없다. 3*3짜리 9칸으로 나눴을 때 영역에 중복된 숫자가 올 수 없다. 이 조건을 잘 생각해서 완전 탐색을 해보자. 입력 빈칸 탐색하기 싫어서 입력을 받을 때 빈칸인 좌표를 zeros에 저장해주었다. 완전 탐색 for(int i=1; i
🔗 문제 2339번: 석판 자르기 2339번: 석판 자르기 하나 이상의 불순물과 보석 결정체로 이루어진 석판을 여러 조각으로 나누어 가공해서, 보다 높은 가치를 얻을 수 있도록 만들려고 한다. 이때, 높은 가치의 석판을 만들기 위해서는 석판을 여 www.acmicpc.net 🖍 풀이 문제를 풀기 위해서는 총 3가지 과정을 정확히 이해해야 합니다. 석판을 자를 수 있는 조건 석판 자르기 재귀적으로 석판 자르기 (내가 막혔던 부분) 석판을 자를 수 있는 조건 이전과 다른 방향으로 잘라야 한다. (가로, 세로의 반복) 자르고자 하는 열이나 행은 불순물을 포함한다. 자르고자 하는 열이나 행에 보석이 있으면 자를 수 없다. 잘랐을 때 반드시 석판이 2개로 나뉘어야 한다. 불순물을 모두 제거한 후 조각난 각각의 보..
🔗 문제 14501번: 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 🖍 풀이 일을 했을 경우와 일을 하지 않았을 경우로 상황을 나눠 생각할 수 있다. i 날에 일을 한 경우: i + T[i] 에 수익이 전에 벌어 놓은 돈 + P[i] 이 된다. i 날에 일을 하지 않을 경우: i+T[i]날 수익에 변동이 없다. 이걸 재귀함수로 짠다면? 간단하게 생각하면 완전 탐색할 수 있다. void solve(int days, int profit) { if(days == N+1) { return; } solve(days + T[days], profit + P[days]); solve(days + 1, profit) } 하지만 재귀함수는 호출된 함수 메모..
🔗 문제 1405번: 미친 로봇 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 🖍 풀이 이 문제 전에 '부분수열의 합'을 먼저 풀며 백트래킹에 대해 알고 푸는 걸 권장드립니다. 조건을 정리해보자. 로봇은 동서남북 중 하나를 한칸씩 N번 이동한다. N은 14보다 작거나 같은 자연수다. 동서남북으로 이동할 확률이 있다. → 확률이 0만 아니면 이동이 가능하다. 재방문하지 않으면서 이동하는게 단순한 이동이다. 그냥 재방문하지 않고 N번 이동하는 확률만 구하면 된다. 상하좌우 한 방향으로만 14번 가도 재방문 ..