Do you believe in you?

문제 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 풀이 유클리드 호제법을 이용하여 주어진 숫자에 모든 경우의 수에 따라 최대공약수를 구하는 문제. 고민했던 부분은 3가지였다. 1. 최대공약수를 구할 두 수를 선택(조합을 이용해서)하는 방법 2. 선택한 두 수를 저장 및 최대공약수 연산 함수에 보내는 방법 3. 항상 큰수를 작은 수로 나누게 숫자를 배치하는 방법 무식하게 일단 구현해보자!는 맘으로 덤볐더니 반복문과 벡터를 좀 많이 썼다... (상세 설명은 주석 참조...) 인터넷을 찾..

[문제] 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net N×M의 행렬로 표현된 맵에서 (1, 1)에서 (N, M)까지 이동할 때 걸리는 최단 경로를 구하는 문제. 이 때, 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타내며 1회에 한하여 벽을 부수고 이동할 수 있다. [풀이] Break 유무를 저장해놓고 한번도 깬 적 없는 벽을 깨가면서 탐색해야 할 것 같은데 그 구조를 못짜겠어서 한참을 헤맸다. 결국 풀이 참조... 이 문제의 핵심은 탐색한 경로를 ..

[문제] 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net [풀이] N이 1일 때, N이 2일 때, N이 3일 때를 손으로 그려보며 규칙을 찾았다. 아래 그림 참조. 즉, N이 1일 때는 가장 큰 값을 제외하고 5개를 더해주면 되고, N이 1보다 클 때는 다음과 같은 공식이 있었다. - 면이 3개 보이는 주사위 개수: 4 - 면이 2개 보이는 주사위 개수: (N-1)*4 + (N-2)*4 - 면이 1개 보이는 주사위 개수: (N-2)*(N-2) + (N-2)*(N-1)*4 공식을 구해서 ..

[문제] 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 55-50+40 같은 식이 주어졌을 때, 괄호를 알맞게 쳐서 최소 합을 구하는 문제 예시 답은 55-(50+40) = -35 이다. [문제풀이] 경우의 수를 여러개 만들어서 계산해보며 규칙을 찾아야 한다. -가 없을 때, -가 가온데 껴있을 때, -가 계속 있을 때, - + 가 반복 될 때 등등... 10+11-5+4 = 10+11-(5+4) = 12 1+10-15-10+20-1 = 1+10-(15+10)+20-(1) = 5 위 두가지 경우를 살펴..

[문제] 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net [문제설명] 스도쿠 게임의 답을 찾는 문제 ~! 스도쿠 게임 조건은 아래 2가지다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. [문제 풀이] 첨엔 예시만 보고 가로, 세로, 3x3을 탐색해서 한칸만 비어서 바로 풀수 있는 칸을 풀고 다음 칸을 푸는 방식으로 구현했다. 결과는 대망... 아래 반례처럼 빈칸이 많을 때도 포함..

[문제] 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net [문제설명] 사회망 서비스(SNS)에 속한 사람들은 얼리 아답터이거나 얼리 아답터가 아니다. 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 어떤 아이디어를 사회망 서비스(SNS)에서 퍼뜨리고자 할 때, 가능한 한 최소의 수의 얼리 아답터를 확보하여 모든 사람이 이 아이디어를 받아들이게 하자. 얼리어답터의 조건은 다음과 같다. - 얼리 어답터가 아니면, 모든 친구들이 얼리 어답터야 한다. - 얼리 어..

문제 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 이 문제를 풀 때 중요한 점은, 물고기를 한마리 먹을 때 마다 그리고 물고기 크기가 늘었을 때 마다 먹을 수 있는 물고기를 재탐색해야 한다는 것이다. 물고기를 한 마리 먹었으면, 그자리로 이동해서 다시 가장 가까운 && 가장 위에 있는 && 가장 안쪽에 있는 물고기를 다시 찾아야하기 때문이다. 그리고 물고기 크기가 늘었다면, 먹을 수 있는 물고기가 늘어날 것이기 때문이다. 물고기를 탐색하는 부분은, 가장 가까운 물고기가 최우선이므로 최단거리 찾기..

[문제] 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 스코빌 지수가 가장 낮은 두가지 음식을 섞어서 모든 음식이 K이상의 스코빌 지수를 가지게 하려 할 때 필요한 최소 연산 횟수를 구하는 것. [풀이] 처음엔 걍 STL algorithm의 sort() 함수로 scoville 벡터를 내림차순 정렬하고 scoville 벡터의 가장 작은 값과 두번째로 작은 값을 K보다 커질 때까지 연산하는 과정을 반복했다. 결과는 효율성 테스트 0점. #include #include using namespace s..

[문제] 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net [문제설명] 인접한 두 칸을 골라서 사탕을 교환한 후, 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 찾는 문제이다. [문제풀이] 이 문제의 함정은 서로 다른 색깔의 인접한 두 칸이 아닌 걍 인접한 두 칸이라는 점인 것 같다. PPPP 처럼 교환하지 않을 때 가장 긴 연속 부분을 가질 수도 있기 때문이다. 나는 인접한 두 칸을 선택하기 위해 int dir[2][2] = { {0,1},{1,0} } 오른쪽과 아래에 해당하는 방향키 배열을 만들었다. 그리고 2중 for문을 사용해서 모든 좌표를 탐색해줬다.(brute force) for (int i = 0; ..

[문제] 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net [문제설명] n가지의 동전이 있을 때, 이 동전들을 적당히 합쳐서 k원이 되게 하는 경우의 수를 찾는 것. [풀이] Bottom-up 방식으로 1을 만드는 방법, 2를 만드는 방법, 3을 만드는 방법, ... 10을 만드는 방법까지 구할 것이다. 이 때, 2,3,...을 만드는 방법을 이전에 구한 값을 이용할 것이다. 문제에서 주어진 1,2,5 동전으로 생각해보면, 1,2,5로 1을 만드는 경우의 수는 1 한가지이다. 1,2,5로 2를 만드는 경우의 수는..