본문 바로가기

전체 글

 (2341)
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 2294번:동전2 답 //d[i] = i원을 만드는데 필요한 최소 동전의 개수//d[i] = d[i-a[j]]+ 1 (d[i-a[j]] !=-1 : d[i-a[j]]==-1라면 애초에 이 값을 만들수가 없다는 뜻이므로 -1이면 안된다)12345678910111213141516171819#include #include using namespace std;int n,k, a[101], d[100001],ans=-1;int main() { cin >> n >> k; for (int i = 1; i > a[i]; } for (int i = 1; i
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 2293번:동전1 답 D[i][j] = i개의 동전을 활용하여 j원을 만드는 경우의 수 1.A[i]를 사용하는 경우 - > A[i-1]까지의 동전을 사용하여 j-A[i]원을 만들어야함 : D[i][j] += D[i-1][j-A[i]] 2.A[j]를 사용하지 않는 경우 - > A[i-1]까지의 동전을 사용하여 j원을 만들어야함 : D[i][j] += D[i-1][j]D[i] += D[i-1][j-A[i]] + D[i-1][j] 이는 1+1+2, 2+1+1, 1+2+1를 모두 다른 경우로 친다.그러므로 이를 막기 위해 D[i] += D[i-A[j]]1234567891011121314151617#include using namespace std;int n, k, a[101], d[10001];int main() { cin >> n..
(C++, Python3) - 백준(BOJ) 1697번 : 숨바꼭질 https://www.acmicpc.net/problem/1697📕 풀이방법📔 입력 및 초기화1. 수빈이의 좌표 n, 동생의 좌표 k를 선언 후 입력받습니다. 2. 현재 탐색할 경로정보를 저장할 deque dq를 선언 후 현재 수빈의 좌표와 시간 0을 초기값으로 넣어줍니다. 3. 각 좌표 check배열을 선언 후 0에서 10만까지 위치에 존재할 수 있으므로 10만1의 크기를 선언해줍니다.📔 풀이과정함수 bfs를 구현해줍니다.1. dq에서 원소를 pop해 현재 좌표 pos가 k인지 비교해 맞다면 해당 time을 반환합니다. 2. 수빈이 현재 좌표에서 갈 수 있는 곳은 x-1, x+1, x*2이므로 범위를 초과하지 않으며 해당 좌표가 방문하지 않았다면 방문처리 후 dq에 append해줍니다. * 도착..
(C++) - 백준(BOJ) 11403 : 경로 찾기(BFS) 답 #include #include #include #include using namespace std; int N,a[101][101],d[101][101],c[101][101]; queue q; void BFS(int t)//정점에 연결되어 있는 간선을 모두 본 후에 마지막에 자신을 거치는 경로가 있는지 살펴본다 { q.push(t); while (!q.empty()) { int x = q.front(); q.pop(); for (int i = 1; i > N; for (int i = 1; i a[i][j]; } for (int i = 1; i
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 11403번:경로 찾기(DFS) 답 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include #include using namespace std;int N,a[101][101],d[101][101],c[101][101],t;queue q;void DFS(int x)//정점 x에 연결되어 있는 모든 간선을 확인하고 경로에 등록한다{ for (int i = 1; i > N; for (int i = 1; i a[i][j]; } for (int i = 1; i
(C++) - 백준(BOJ) 2252번 : 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬 문제였습니다. 풀이방법 1. 단 방향그래프로 만듭니다. 2. dfs를 수행하면서 모두 호출한 후에는 stack에 정점을 push해줍니다. 3. 모든 원소를 stack pop하면서 출력합니다. Code indegree이용하는 법 #include #include #include using namespace std; int N,M,u,v,ins[320..
(C++) - 백준(BOJ) 11723 : 집합 #include #include using namespace std; int M, S, n; char k[10]; int main() { scanf("%d", &M); while (M--) { scanf("%s", k); if (!strcmp(k, "add")) { scanf("%d", &n); n--; S = (S | (1
(C++) - 백준(BOJ)코딩 1149번 : RGB거리 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2차원 bottom up dp로 풀었습니다. 풀이방법 D[i][j] = i번째 집을 j색으로 칠할 때 최소 비용 빨강:1 초록:2 파랑:3 D[1][1] = A[1][1]; D[1][2] = A[1][2]; D[1][3] = A[1][3]; A[i][j] = 입력 j로 칠했을 때 i-1, i+1번째 집은 j색으로 칠할 수 없다. 1.i번째 집을 R로 칠했을 때 (2

티스토리툴바