레벨3
-
[프로그래머스] N으로 표현알고리즘/프로그래머스 2021. 8. 17. 21:18
문제 링크 풀이 많은 DP 문제가 그렇듯 점화식만 제대로 세울 수 있으면 어렵지 않은 문제이지만, 꽤 까다로운 문제에 속하는 것 같습니다. 여기에서 d[i]는 solution 함수의 매개변수로 주어지는 N을 i번 사용해서 얻을 수 있는 숫자의 집합으로 정의해 문제를 풀면 수월합니다. 즉 N이 5라면 다음과 같은 점화식을 만들 수 있습니다. d[1] = {5} d[2] = {55, 5+5, 5-5, 5*5, 5/5} d[3] = {555, (5+5) + 5, (5+5) - 5, (5+5) * 5, ... , 55 / 5} 3번째 항부터는 집합의 크기가 커지기 시작합니다. 우리는 규칙을 찾아야 하고요. 일단 N이 i만큼 붙어 있는 숫자 하나는 만들기 쉽습니다. d[4]에는 5555가 있겠지요. d[2]를 보..
-
[프로그래머스] 가장 먼 노드알고리즘/프로그래머스 2021. 8. 16. 15:20
문제 링크 풀이 bfs를 이용하면 방문하는 노드가 최단거리가 됩니다. 거리를 기록하는 배열인 dist를 이용해 지금 노드에서 다음 노드를 방문할 때 +1을 해서 값을 갱신합니다. 코드 #include #include #include using namespace std; int solution(int n, vector edge) { int answer = 0; vector vec(n + 1, vector(n + 1)); size_t size = edge.size(); for (int i = 0; i < size; ++i) { auto n1 = edge[i][0]; auto n2 = edge[i][1]; vec[n1][n2] = 1; vec[n2][n1] = 1; } vector visited(n + 1, ..