순간을 성실히, 화려함보단 꾸준함을

www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 : 동혁이가 가고 싶어하는 도시를 갈 수 있는지 없는지 구하시오 해설 : 다른 분들은 disjoint-set 개념을 이용해서 푸셨는데, 전 그냥 dfs 한번 돌렸습니다. 결국 동혁이가 같은 도시를 여러번 방문 하던 안하던 시작점에서 한번 dfs를 돌렸을때 못가는 도시는 평생 가지 못하기 때문이죠. #include using namespace std; int n,m; int adj[210][210],arr[..

www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 문제 : 사칙연산을 해서 s->t 로 만들 수 있을때 연산동작을 출력하여라, 이때 사전순으로 앞서있는 문자열을 먼저 출력 해설 : 간단하게 dfs나 bfs를 사용해서 풀면 됩니다. 다만 이제 범위가 n이 10억인걸 유의해야겠죠. 이미 방문을 하였는지 체크하기 위해선 단순 배열로는 무리라는 것을 알 수 있습니다. 메모리가 감당이 안되기 때문이죠 그럼 우린 다른 방법을 택해야 되는데 자료구조 중에 set 이..

www.acmicpc.net/problem/2982 2982번: 국왕의 방문 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안 www.acmicpc.net 문제 : 국왕이 방문하는데 이때 교차로 사이의 도로는 국왕이 먼저 건너면 건널 수 없습니다. 이때 상그니가 목적지까지 최소시간으로 갈 수 있는 시간을 구하시오 해설 : 아우 전 문제를 잘못 읽어서 엄청 고생했었습니다. 교차로에는 공유 가능하나 교차로 사이의 도로가 겹치면 안되는 것 입니다. 이때도, 상그니가 먼저 교차로에는 들어갈 수 있습니다. 무조건 국왕이 먼저 도로를 건너면 건너지 못합니다. 다익스트라 알고리즘을..

www.acmicpc.net/problem/1503 1503번: 세 수 고르기 첫째 줄에 N(1 ≤ N ≤ 1,000)과 집합 S의 크기 M(0 ≤ M ≤ 50)이 주어진다. 둘째 줄에는 집합 S에 들어있는 수가 주어진다. 집합에 들어있는 수는 1,000보다 작거나 같은 자연수이고, 공백으로 구분되어 www.acmicpc.net 문제 : 집합 S에 속한 수들이 주어지고 N이 주어집니다. 이때, 집합 S에 속하지 않은 수들 중 x,y,z 를 선택하고 |N-xyz|의 값이 최소값을 구하시오 해설 : 문제 잘 읽고 오세요!!! x,y,z는 중복이 가능한가 가능하지 않는가 문제에 나와있질 않지만 중복이 허용됩니다!!!! n의 범위가 1000이니 가볍게 삼중포문을 통해 x,y,z를 확인하면서 경우의 수를 구하면 ..

www.acmicpc.net/problem/17208 17208번: 카우버거 알바생 중간고사 종료를 기념해 계획 없이 돈을 쓰던 영석이는 안타깝게도 통장 잔고가 100원도 남지 않게 되었고, 결국 영석이는 카우버거 주방 알바를 하기로 했다. 카우버거는 치즈버거와 감자튀 www.acmicpc.net 문제 : 치즈버거와 감자튀김이 남았다. 이를 이용해서 최대로 많이 주문을 받을 수 있는 수를 구하자 해설 : dp는 언제나 어렵습니다....(저에게 ㅠ) 먼저 전 치즈버거와 감자튀김의 변수를 이용하여 2차원 dp테이블로 작성해보려 했습니다. 그러나 문제가 생기는데 바로 '동일한 치즈버거와 감자튀김이 남았을 경우 그 값이 최적의 값이 아니게 됩니다' 그 이유는 주문하는 순서를 고려하고 풀어나가야 되는데 그러지 못..

www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 문제 : 주어진 수들을 조합해서 만들 수 없는 수들중 가장 작은 수를 구해라 해설 : n이 최대 20이니 모든 경우의 수를 해보면 되겠죠. 그리고 만들 수 없는 수를 구하기 위해선 만들 수 있는 수를 체크해 두고 1부터 200만 까지 증가시켜가며 만들 수 없는 수들 중 가장 작은수를 구하면 됩니다. 만들 수 있는 수들을 set에다가 저장해 두면..

www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net 문제 : 각 팀원들이 풀 수 있는 문제가 주어지고 모든 문제를 풀 수 있는 팀원들의 조합이 최소의 수가 되는 수를 구해라 풀이 : n이 최대가 10 이니 그냥 맘편하게 모든 경우의 수를 돌려보면 됩니다. 재귀함수를 이용해서 depth==m 일때 조건에 맞는지 확인하고 맞으면 최소값을 갱신시켜주는 식으로 풀면 되겠죠 #include using namespace std; int n, m; int vi..

www.acmicpc.net/problem/1821 1821번: 수들의 합 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있 www.acmicpc.net 문제 : 파스칼 삼각형의 형태로 수들이 존재합니다. 맨 윗줄은 1부터 n까지의 수들만이 주어지고 맨마지막 수를 만들수 있는 수열을 구하는 문제입니다. 해설 : permutation의 개념을 알고 있고, 이를 구현할 수 있으면 쉽게 풀 수 있는 문제입니다. 만약 permutation이 뭔지는 알지만 어떻게 구현하는지 모르겠다는 분들은 이번 기회에 무조건 무조건 습득하시고 외우세요....뇌속에 박아 놓으..

www.acmicpc.net/problem/2091 2091번: 동전 첫째 줄에 다섯 정수 X(1 ≤ X ≤ 10,000), A, B, C, D(0 ≤ A, B, C, D ≤ 10,000)가 주어진다. www.acmicpc.net 문제 : 1,5,10,25 센트가 각각 존재합니다. 이때 x를 만들수 있는 경우의 수 중 가장 많은 동전을 사용했을때 각각의 센트수를 출력하시면 됩니다. 해설: 이 문제 현재 골4로 측정되어있는데 절대 아닌 것 같아요,,,,,(갓님들 티어조정좀 ㅠㅠㅠ) 일단 다양한 방법이 존재하는 것 같습니다.(그리디,다이나믹 프로그래밍,브루트 포스) 그러나 전 dp 와 dp+브루트포스 로 풀었는데 그냥 dp 로 푼 걸로 설명하겠습니다.(브루트 포스 궁금하시면 댓글로 남겨주세요) 점화식을 어떻..

www.acmicpc.net/problem/2937 2937번: 블록 정리 민혁 유치원에서는 아이들의 창의력과 인내력, 근력과 지구력, 잉여력과 탄성력, 판단력과 노력, 기력과 활동력, 활력과 달력, 내구력과 변형력, 응집력과 무력, 지력과 매력, 미력과 담력, 능력 www.acmicpc.net 문제 : 블록들이 막 쌓여져 있고 이를 옮겨서 직사각형을 만들고 싶다. 이때 보드의 한칸에 블록이 2개 이상 쌓이면 안되도록 만들어라. 해설 : www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 ..

www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 문제 : a와 b만 주어진 문자열이 있고, a를 연다라 놓고 싶을때 최소한으로 교환해야되는 횟수를 구하시오 해설 : 이런 문제가 은근히 안보이면 계속 안보입니다. 모든 문제를 접하게 될때 가장 중요한 개념 중 하나는 어떻게 하면 문제를 최대한으로 간소화 시킬 수 있을지 부터 생각해 보는겁니다(djm03178 님의 말씀입니다) 그러면 문제를 한번 봅시다. 우린 일단 직관적으로는 누구나 다 알고 있습니다. "요놈 a랑..

www.acmicpc.net/problem/1469 1469번: 숌 사이 수열 첫째 줄에 X의 크기 N이 주어진다. 둘째 줄에 X에 들어가는 수가 빈칸을 사이에 두고 주어진다. X의 크기는 10보다 작거나 같은 자연수이다. X의 원소는 0보다 크거나 같고 20보다 작거나 같은 정수 www.acmicpc.net 문제 : 현재 위치한 수와 같은 수 사이에는 이 수 만큼 수들이 존재하도록 수열을 만들어라 해설 : ,,,,,,이 문제 드럽게 힘들게 풀었습니다. 먼저 이 문제를 통해 브루트포스 부분이 약하다는 걸 뼈저리게 느꼈습니다.(열심히 다시 문제를 쭉쭉 풀어나가야겠어요) 첫번째로 막연하게 생각해볼 수 있는 방법은 '순열'입니다. 예제 케이스로 보면 112233 의 6개의 숫자들을 332211까지 돌아보면서 ..