본문 바로가기

코딩테스트_백준풀이54

스티커 #9465 c++ 풀이 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 틀린 코드 : #include #include using namespace std; int T; int n; int s[2][100001]; int dp[2][100001]; int main() { cin >> T; while (T--) { memset(dp, 0, sizeof(dp)); memset(s, 0, sizeof(s)); cin >> n; for (int i = 0; i < .. 2023. 11. 8.
RGB거리 #1149 c++ 풀이 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집을 색칠할건데, 비용이 가장 작은 경우를 출력하라는 dp문제이다. 경우의 수는 다음과 같다. 이번에 R을 칠할 것이면, 다음에는 GB중 하나를 선택해야한다. 이번에 G을 칠할 것이면, 다음에는 RB중 하나를 선택해야한다. 이번에 B을 칠할 것이면, 다음에는 RG중 하나를 선택해야한다. 3가지 경우의 cost를 전부 세야하는구나를 알았다. 따라서 RGB로 시작하는 각각의 비용.. 2023. 11. 6.
N과 M 시리즈 ( 순열, 조합, 중복순열, 중복조합 ) 15649, 15650, ..등등 N과 M을 받았을때 순열과 조합을 만드는 코딩 문제를 해결하면서, dfs에 대해서 깊게 생각해볼 수 있는 계기가 되었다. 1. 정의 2. 코딩 3. 예제 순으로 글을 쓸 것이다. 나름의 정의를 내린다. 순열 : 순서에 따라 결과가 달라지는 수의 모임 {1,2,3} != {2,1,3} 조합 : 순서가 상관없는 수의 모임 {1,2,3} == {2,1,3} 순열과 조합의 코딩스타일을 이해하기 위해서 https://yabmoons.tistory.com/99 [ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++) 브루트포스 알고리즘에서 가장 많이 사용되는 방법이 순열과 조합등으로 모든 경우의 수를 모두 계산해본 뒤에 원하는결과 값을 찾는 방식이다. 이 글에서는, .. 2023. 11. 2.
A -> B #16953 c++ 풀이 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net bfs가 단방향으로 한번만 도는 경우, visited가 필요없을 수 있겠구나 하는 생각이 들었다. #include #include using namespace std; long long int A, B; //int graph[100000000]; //int visited[100000000]; int cnt; void bfs(long long int A) { queue q; q.push(make_pair(A,0)); while (!q.empty()) { long long int curr = q.front().first; l.. 2023. 11. 1.

티스토리툴바