분류 전체보기

백준 1149 RGB거리 c++ // dp, 테이블정의(2차원)

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1. 문풀 및 전체코드 #include using namespace std; //i번째 집을 j색으로 칠했을때 최소비용, 칠한색깔(0:빨, 1:초, 2:파) int d[1004][3], a[1004][3]; int n; /* * d[1][0] * d[1][1] * d[1][2] * * d[k][0] : max(d[k-1][1]+a[k][0], d[k-1][2]+a[k][0])..

백준 2579 계단오르기 c++ // dp , 제약조건이 있으면 2차원 dp로 테이블을 정의하라.

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 1. 전체코드 #include using namespace std; /* * DP * 1. 테이블정의 * 2. 점화식 for문 * 3. 초기값 정하기 */ /* * * 1. 테이블정의 * d[i][j] : 현재까지 j개의 계단"연속" 밟음, i번째 계단까지 왔을때 점수합의 최대값 i번째 계단을 꼭 밟아야함. 2.점화식 d[k][1] : k번째 계단까지왓는데 "연속" 1개밟음->자기자신임->d[k-1]은 안밟 ..

백준 9095 1,2,3더하기 c++ // dp 기준으로 나눠서 규칙을 찾아라

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 1. 풀이과정 및 전체코드 d[4]를 기준(맨끝에 더하는수)로 정렬후 규칙을찾고 일반화 한다. #include using namespace std; /* * DP * 1. 테이블정의 * 2. 점화식 for문 */ //1. d[i] : i를 1,2,3의 합으로 나타내는 방법의 수 /* * d[1]=1 * d[2]=1+1 d[1] / 2 / * d[3]=1+1+1 d[1] / 1+2 d[2]+1 / 2+1 d[2]+1 / 3 / * 기준 : 맨뒤에 더하는 숫자 * d[4]=1+1+1+1, 3+1, ..

백준 1463 1로만들기 c++ // dp 하는 방법

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. dp 하는 방법 /* * DP * 1. 테이블정의 * 2. 점화식 for문 (초기항은 직접구함) */ 1.1 점화식 구하는방법 구체사례를 일반화 하라. d[12] = d[4]+1 , d[6]+1 , d[11]+1 중 최소값 d[i] = d[i/3]+1 , d[i/2]+1 , d[i-1]+1 중 최소값 2. 최소값 구하는 방법(3개숫자 이상일때) 첫번째 값 대입후 새로운 값이 들어올때마다 min (자기자신, 새로운값) 해주면 된다. d[i] = d[i - 1] + 1; if (i % 2 == 0) { d[i..

프로그래머스 의상 c++ // 해쉬 , 경우의수 , 백트래킹

https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제해결 ex) 모자 : 3개 상의 : 2개인경우 모자 : 안입음, 1개입, 2개입, 3개입 상의 : 안입, 1개입, 2개입 모든경우의수 == 4*3==12 에서 안입는경우 -1을 하면된다. 2. 코드 #include using namespace std; int ret; map m1; map m2; int solution(vector clothes) { for(auto v : clothes)..

백준 16987 계란으로 계란치기 c++ // 백트래킹, 원상복구, 다음깊이로 넘어가는 방법

https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 1. 다음깊이로 넘어가는 방법 if(조건){ go(k+1); return; } 하면된다. 2. 의사코드 3. 내 전체코드 #include using namespace std; int n, v[10], ret; vector eggs; //현재 k번째 계란을 들고 깨려고함 void go(int k) { if (k >= n) { int died_count = 0; for (auto p :..

[틀림] 백준 1941 소문난 칠공주 c++ // 1차원배열을 2차원좌표로 매핑하는법 , 백트래킹, dfs

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작www.acmicpc.net1. 1차원배열을 2차원좌표로 매핑하는법 1차원 idx : 0 1 2 3 4 5 6 7 8 9 ...... 242차원 : (0,0) (0,1) ....               (4,4)y좌표 == 1차원idx /5x좌표 == 1차원 idx %5 하면 된다!  2. 풀이과정1. 25C7로 인덱스를 조합한다. (방문할 대상들의 좌표를 조합)2. idx로 배열에 접근 후 , s_cnt>=4인지 검사ㅡㅡㅡㅡㅡㅡ..

백준 6603 로또 c++ // kC6 구현하기

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 조합 - isused사용 => 중복조합아님 2. 전체코드 #include using namespace std; int n,k; int a[15], isused[15], arr[15]; //현재 q개뽑았음 void go(int q) { if (q == 6) { for (int ..