본문 바로가기
반응형

알고리즘38

[cpp 알고리즘] 백준 20152 Game Addiction [백준] 20152 Game Addiction cpp 풀이알고리즘: 수학, 다이나믹 프로그래밍(DP), 조합론https://www.acmicpc.net/problem/20152문제 요약- 집의 좌표(H,H) 에서 PC 방의 좌표(N,N)가 주어진다.- 좌표평면(x,y)에서 y>x인 곳은 갈 수 없다. - 집에서 PC방까지 경로의 개수를 구해야 한다. (단, 상하좌우 방향으로 이동할 수 있고 한 번 이동할 때 거리는 1이다. 또한 항상 최단 경로로 움직인다.)풀이 정리- 최단경로라는 말에 처음에는 bfs로 생각을 하다가, 뒤로 갈 수록 너무 많고 생각보다 규칙이 보여서 dp로 접근했다.- 아래 사진처럼 예제들을 직접 따라 그려보면 어떻게 구하는지 바로 알 수 있다. (지금 보니까 집이랑 PC방 위치를 반대.. 2024. 7. 15.
[cpp 알고리즘] 백준 19844 단어 개수 세기 [백준] 19844 단어 개수 세기 cpp 풀이알고리즘: 구현, 문자열https://www.acmicpc.net/problem/19844 문제 요약문제가 너무... 어렵게 적혀있는 것 같다. 해야하는 것을 쉽게 정리하자면먼저 띄어쓰기와 -(하이픈)을 기준으로 “단어”를 쪼갠다.각각의 “단어”에서, 위처럼 줄어들었을 가능성이 있는 경우(즉, c', j', n', m', t', s', l', d', qu'로 시작하고 어포스트로피 뒤 글자가 모음인 경우) 이 단어들을 한 번 더 분리해 준다.핵심은 여기서 '(어포스트로피) 앞에는 단어(c,j,n,m,t,s,l,d,qu) 가 있어야 하고, '(어포스트로피) 뒤에는 모음(a,e,i,o,u,h)로 시작하는 단어가 오면 된다. =>  ' 앞에는 단어 단위로, ' 뒤에.. 2024. 7. 15.
[cpp 알고리즘] 백준 20364 부동산 다툼 [백준] 20364 부동산 다툼 cpp 풀이알고리즘: 트리https://www.acmicpc.net/problem/20364 문제 요약이진 트리 모양의 땅으로 이루어진 마을이 있다. - 루트 땅 번호는 1이다.- 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2*K, 오른쪽 자식 땅의 번호는 2*K+1이다. 오리들이 땅을 분배받는데,- 맨 처음 오리부터 원하는 땅을 배정받는다. - 한 오리가 원하는 땅 까지 가는 길에 이미 다른 오리가 점유하고 있다면, 그 오리는 땅을 가지지 못한다.  오리가 원하는 땅을 가질 수 있다면 0을, 가질 수 없다면 처음 마주치는 점유된 땅의 번호를 출력하면 된다.풀이 정리(1) 입력받은 근손실 정도를 (오름차순으로) 정렬한다. (2-1) 운동기구 개수 N이 홀수인 경우에.. 2024. 7. 10.
[cpp 알고리즘] 백준 20300 서강근육맨 [백준] 20300 서강근육맨 cpp 풀이알고리즘: 그리디 알고리즘, 정렬https://www.acmicpc.net/problem/20300 문제 요약- 헬스장에 있는 N개의 운동기구 중에 하루에 2개의 운동기구로 운동한다. 홀수 개의 운동기구가 있는 경우에는 마지막 PT를 받을 때는 운동 기구를 하나만 사용한다.- 이 때 운동기구마다 근손실이 일어나는 정도가 다르다. PT를 한 번 받을 때의 근손실 정도가 M을 넘지 않도록 하고 싶다. 이때, M의 최솟값을 구하는 문제이다. (운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.)풀이 정리(1) 입력받은 근손실 정도를 (오름차순으로) 정렬한다. (2-1) 운동기구 개수 N이 홀수인 경우에는, 근손실 정도가 최댓.. 2024. 7. 9.
반응형

티스토리툴바