본문 바로가기

전체 글199

[프로그래머스] 도둑질 c++ 풀이 첫번째 집과 마지막 집에 옆에 있으므로 마지막 집을 털게되면 첫번째 집을 털지 못한다. 처음부터 첫번째 집을 터는 경우와 털지 않는 경우로 나누어서 구해야한다. dp[i] 는 i까지 터는 경우의 최댓값이다. 2번 전 집을 털고 i번째 집을 터는 경우와 털지 않고 i-1번째까지의 최댓값을 가져오는 경우가 있다. #include #include #include using namespace std; vectordp1; vectordp2; int solution(vector money) { int answer = 0; dp1.resize(money.size()); dp2.resize(money.size()); int money_size = money.size(); //첫번째 집을 터는 경우 dp1[0] =.. 2024. 2. 6.
[프로그래머스] 사칙연산 c++ 풀이 매번 괄호 안을 연산해주면 시간이 많이 걸리기 때문에 괄호안의 결과를 저장해서 계산해주었다. dp를 이용해 풀었다. 연산이 더하기냐 뺴냐에 따라 최댓값을 만드는 방법이 달라진다. +일때 : (최댓값)+(최댓값) -일때 :(최솟값)-(최댓값) 그러므로 괄호안의 연산의 최솟값도 dp를 이용해 구해놓아야한다. #include #include #include #include using namespace std; vectordp_max(202,vector(202,-10000000)); vectordp_min(202,vector(202,10000000)); vector arr; int calculate(int start, int end,int isMax){ if(isMax & (dp_max[start][end.. 2024. 2. 5.
[프로그래머스] 등굣길 c++ 풀이 (1,1)에서 (m,n)까지 가는 최단 경로의 개수를 구해야한다. 중간에 물웅덩이를 지날 수 없다. m이 x축이고 n이 y축이다. puddles도 (x축 좌표, y축 좌표)이다. 예시로 준 물웅덩이가 2,2라 헷갈릴 수 있다. 1. 물웅덩이의 값을-1로 설정한다. 2. i,j까지 오는 경우의 수는 (i-1,j)와 (i,j-1)에서 오는 경우의 수뿐이다 (오른쪽과 아래쪽으로 밖에 못 움직인다.) 3.두 방향에 각각 물웅덩이가 있는지 검사하고 없다면 경우의 수를 더한다. 4.물웅덩이는 지나갈 수 없으므로 더하지 않고 continue해준다. #include #include #include using namespace std; vectordp(101,vector(101,0)); int solution(in.. 2024. 2. 2.
[프로그래머스] N으로 표현 c++ 풀이 dp를 이용해 풀었다. 임의의 숫자 i에 대해서 N으로만 표현하는 최소 횟수를 구해야하는 문제이다. 사칙연산을 할 수 있기때문에 i에 대해 +,-,*,/를 해주어서 최소횟수를 갱신시켜주었다. dp 배열의 초기화는 N이 1일때는 최소 N번으로 표현할 수 있고 (1+1+1...) N이 1보다 클 때는 N*2번으로 표현할 수 있다. (2/2 + 2/2 + .. ) 또한 N으로만 이루어져있는 숫자들은 따로 초기화를 해주었다. N=5, dp[5]=1 ,dp[55]=2 , dp[555] =3 #include #include #include #include #include using namespace std; vector dp; int solution(int N, int number) { int answer =.. 2024. 2. 1.

티스토리툴바