문제https://www.acmicpc.net/problem/1948문제 설명모든 도로가 일방통행이고, 사이클이 없는 나라가 있다.이 나라의 지도를 그리기 위해 무수히 많은 사람들이 시작 도시에서 출발하여 도착 도시까지 가능한 모든 경로를 탐색한다.모든 사람들이 각자의 일을 마치고 도착 도시에서 만났을 때, 최소 몇시간 후에 만날 수 있을까?모두가 만나기 위해서는 마지막 사람까지 도시에 도착해야 한다.어떤 사람은 이 시간에 만나기 위해, 1분도 쉬지 않고 달려야 한다.출발 도시로 들어오는 도로와, 도착 도시에서 나가는 도로는 0개이다.이 때 도로의 수를 구한다. 풀이처음 문제를 보고 무엇을 구하라고 하는 것인지 이해하기 힘들었다.모든 사람들이 일을 마치고 도착 도시에서 만나야 한다. 즉 가장 늦은 사람까..

문제https://www.acmicpc.net/problem/17287문제 설명대괄호, 중괄호, 소괄호, 0에서 9까지의 숫자로 이루어진 문자열 S가 주어진다.문자열 S에 포함된 숫자들은 점수를 휙득하게 된다.대괄호 안에 있는 숫자는 3점중괄호 안에 잇는 숫자는 2점소괄호 안에 있는 숫자는 1점한 숫자가 여러 개의 괄호 안에 있는 경우 각 괄호의 점수를 합한 값이 그 숫자의 점수이다.이 때 같은 숫자가 여러 개 있더라도 위치가 다르면 점수를 따로 계산한다.나올 수 있는 높은 점수를 출력한다.풀이스택을 통해 괄호를 제거해가면서 숫자가 나왔을 때 스택에 존재하는 괄호의 수 만큼 점수를 넣어주면 된다.이 때 숫자가 여러 개 존재할 때 각각 점수를 다르게 넣어준다는 점이 이 문제의 포인트인 것 같다. scor..

문제https://www.acmicpc.net/problem/2295문제 설명N개의 자연수들로 이루어진 집합 U가 있다.집합 U에서 세 개의 수를 골라 그 합이 U 집합에 존재한다면 그 합이 가장 큰 경우를 찾는다.세 개의 수 x,y,z는 중복이 가능하다. 풀이집합 U의 최대 크기는 N의 최대인 $10^3$이다.세 개의 수가 들어갈 수 있는 모든 경우의 수를 탐색하려면 $N^3 = 10^9$이므로 시간초과가 발생한다.따라서 특수한 방법을 통해 시간 소요를 줄여 문제를 해결해야 한다. 집합 U가 존재할 때 x,y,z를 세 개의 수, k를 세 수의 합이라고 가정하자. 이 때 x+y+z와 k는 모두 집합에 존재한다.즉 $x+y+z = k$라는 식을 세울 수 있다. 이 식을 약간 변영해보자.$x + y ..

문제https://www.acmicpc.net/problem/11387문제 설명크리와 파부는 좋은 무기를 장착해서 전투력을 높이려고 한다. 전투력의 공식은 아래에 있다.크리와 파부가 본인의 무기를 장착했을 때 각 능력치 수치, 그리고 무기를 장착했을 때 증가하는 각 수치가 입력으로 주어진다.이 때 서로의 무기를 바꿔 꼈을 때 전투력이 증가하는지, 감소하는지, 변화가 없는지 검사한다. 풀이이 문제는 부동소수점 오차를 노려 오답을 유도하는 문제다. 부동소수점은 모든 실수를 정확하게 표현이 불가능하기 때문에 모든 수를 정수의 계산이 되도록 바꿔주어야 한다.따라서 실수 계산이 포함된 모든 식에 동일한 수를 곱한 후 전투력을 계산했다. 현재 무기를 장착한 상태의 크리와 파부의 전투력을 계산한다.상대의 무기를 ..

문제https://www.acmicpc.net/problem/11562문제 설명 건물이 n개 건물 간 이동 가능한 길 m개가 주어진다.이 때 길은 양방향 혹은 단방향으로주어진다.건물 s에서 건물 e로 가고 싶을때, 최소 몇 개의 단방향 길을 양방향으로 바꿔야 도착지로 갈 수 있는지 출력한다. 풀이이 문제에서 시작점에서 도착점까지 갈 수 있는 경로를 계산하기 위해서는 모든 경로를 확인해보아야 한다.Ex) 1->4라면 1->2->4, 1->3->4,... 등 모든 경로를 탐색한다.따라서 시작점 -> 경유지 -> 도착점 순으로 시작점에서 도착점을 갈 때 도로를 몇 번 바꿔야 하는지 매번 갱신한다.즉, 경유지를 거쳐 모든 경로를 탐색하는 알고리즘인 플로이드 워셜을 사용해서 최단 거리를 갱신했다.b..

문제https://www.acmicpc.net/problem/18430문제 설명 N*M크기의 직사각형 형태의 나무 재료 배열이 주어진다.각 칸에는 해당 칸을 사용하기 위한 강도가 입력된다.해당 나무 배열에서 'ㄱ'모양의 부메랑을 만들 수 있는 만큼 만든다.이 때 ㄱ자에서 가운데 칸은 2배의 강도를 받는다.이 때 만들 수 있는 모든 부메랑의 강도의 합의 최댓값을 구한다. 풀이시작 지점부터 순차적으로 좌표를 탐색하면서 해당 위치에서 부메랑을 만들 수 있으면 만들고 불가능하면 다음 좌표로 이동하는 방식으로 백트래킹을 통해 최댓값을 구했다. 이 때 문제가 하나 발생했다. 다음 부메랑을 만들기 위해서는 현재 어디 좌표까지 탐색했는지를 판단해야 하는데, 2차원 좌표로는 이전 좌표를 기억해서 해당 위치부터 탐색..

문제https://www.acmicpc.net/problem/14651문제 설명3개의 숫자(0,1,2)만 가지고 N자리 3의 배수를 만든다.N자리로 만들 수 있는 배수의 개수를 구한다. 풀이(0,1,2) 세 가지 숫자로 만들어지는 숫자는 3으로 나누었을 때 나머지가 0,1,2만 나오게 된다.따라서 나머지가 동일한 숫자 별로 나누어서 보면, 규칙을 찾을 수 있다.간단하게 예시를 들어보자. 나머지012N = 212, 2110, 2211, 20 N = 3120, 210, 102, 222, 111, 201,,,,,,N = 2일 때 나오는 각 나머지 별 숫자의 개수는 2개이다. 결국에는 뒤에 숫자가 돌림이 되기 때문에 각 나머지 별 숫자는 동일하게 생성된다. 여기서 우리가 알아야 할 정보는 나머지가 0인 수(3의..

문제https://www.acmicpc.net/problem/6219문제 설명A와 B 사이의 소수가 숫자 D를 포함하는지 검사한다.숫자 D를 포함한 소수의 개수를 구한다. 풀이에라토스테네스의 채를 통해 소수를 찾은 후, A와 B 사이의 소수가 숫자 D를 포함하는지 확인 후 카운트한다.에라토스테네스의 채를 통해 2부터 B까지 소수를 전부 탐색한다.A에서 B까지 탐색하면 해당 숫자가 D를 포함하는지 검사한다.이 때 숫자를 스트링으로 변경하여 문자열 내 D 문자가 포함되어 있으면 카운트한다.코드import sysinput = sys.stdin.readlinedef p(): board = [i for i in range(b+1)] board[1] = 0 for i in range(2,b+1):..

문제https://www.acmicpc.net/problem/1813문제 설명 아래와 같은 N개의 말이 주어진다.정확하게 a개의 말은 참이다.정확하게 b개의 말은 참이다.....이 중 몇개의 말이 참인지 구해라.가능한 답이 여러가지라면 가장 큰 값을 출력한다.모순일 경우 -1를 출력한다.풀이예시를 1개 들어보자."정확하게 3개의 말이 참이다." 라는 문장이 참이 되려면, 해당 문장이 총 3번 나와야 정답이다. 즉 a개의 말이 참이려면, 문장이 a번 나와야 한다. 이런 특성을 이용해서 딕셔너리에 카운팅을 해서 개수가 같으면 답을 갱신한다. 딕셔너리에 각 문장의 a를 카운팅한다.모순이 나올 경우 결과를 -1로 변경한다.모순이지만, 정답이 존재하는 경우는 정답을 출력한다. 코드import s..

문제https://www.acmicpc.net/problem/19538문제 설명 최초 유포자부터 시작하여 루머를 퍼트린다.매 분 루머를 믿는 사람은 모든 주변인에게 루머를 동시에 퍼트린다.이 때 주변인의 절반 이상이 루머를 믿고 있다면, 본인도 루머를 믿는다.사람들이 루머를 처음 믿기 시작하는 시간을 구한다. 풀이문제만 읽어보았을 때는 단순 탐색의 냄새가 강렬하게 난다. 따라서 처음에는 단순 BFS로 접근했다가 문제를 찾았다. 문제의 핵심 포인트는 설명에 나와있다.매 분 루머를 믿는 사람은 주변인에게 루머를 퍼트린다. 즉 루머를 믿는 사람만 퍼트리기 때문에 방문 탐색을 바로 진행하는 것이 아니라, 다음 사람이 루머를 믿게 될 때만 방문처리를 하고 다음 탐색 큐에 넣어주면 된다.탐색 전 사람 별 몇 명을..