알고리즘/SW EXPERT 썸네일형 리스트형 5644. 무선충전 5644. 무선충전 시뮬레이션 문제. 조금 문제를 충실히 생각해봐야 했던 문제였다. 일단 내가 생각하던 x, y 좌표가 아니어서 내 방식으로 바꿔주는 부분에서도 헷갈렸다. 문제의 그림만 처음 봤을때는 BFS를 생각했지만, 문제 상에서 그냥 거리 D를 이용하면 따로 BFS를 사용하지 않아서 간단해졌다. p[i][j] 를 통해서 i 시간에 좌표들의 위치를 저장하였다, 즉 j=0 일때는 0번 사람, j=1 일때는 1번 사람의 위치가 된다. 전체적인 흐름으로는 주어진 시간을 0초부터 끝까지 돌면서 각 점에서 닿을 수 있는 BC중 가장 Power 가 쌘놈을 찾는다. 단 이 과정에서 닿 을 수 있는 BC가 여러개인 놈을 체크하기 위해, cnt 라는 갯수를 세는 변수를 추가했다. 가장 쌘놈이 교집합일 때는 케이스를 .. 더보기 1247.최적경로 1247. 최적경로문제에서 나와있듯이 그냥 모든 경로를 탐색하면서 최소값을 찾아주어도 시간제한이나 메모리제한에 걸리지 않는다. 그래서 그냥 부르트포 스를 이용해서 문제를 해결했다. 한 집의 위치정보와 그 집을 방문했는지 여부를 구조체를 이용해서 만들어주었다. house 변수의 0번째를 출발하는 집으로, 1번째를 도착하는 집으로 설정하였고, 재귀함수를 이용해서 모든 경우를 탐색하였다. 재귀함수의 매개변수로 이전의 값들을 저장하면서 거리를 구하면서 재귀함수를 실행시켰다. 그리고 마지막으로 도착점과 그 이전 점과의 거리를 더해주고 정답과 비교하면서 최소값을 찾아냈다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444.. 더보기 5213. 진수의 홀수 약수 5213. 진수의 홀수 약수 숫자의 범위가 커서 시간제한이 문제일 것 같았다. 따라서 testcase 를 받기전에 get_f 함수를 통해서 각각의 f[x] 값들을 미리 구해주었다. 그리고 조금 더 시간을 단축하기 위해서 sum 이라는 배열을 통해서 sum[x] 는 1~X 까지 f[X] 의 합을 구했다. 따라서 정답을 구할 때는 sum[R]-sum[L-1] 을 통해서 구할 수 있었다. get_f 에서 최대 루트 1000000 까지 돌고, main 함수에서 1000000 번 돌기 때문에 1억번으로 시간제한을 통과할 것이라고 생각하고 코드를 구현하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#incl.. 더보기 1248. 공통 조상 1248. 공통 조상 공통 조상 같은 경우에는 LCA라고 하여, 해당하는 노드의 높이를 맞춰준 후에 같이 부모 노드로 거슬러 올라가면서 같은 노 드가 될 때까지 while 문을 이용하여 구할 수 있습니다. 또한 문제에서 해당하는 조상 노드의 서브 트리의 크기를 구하라고 하였는데, 이는 분할정복을 이용하여 get_size() 함수에 서 자식 노드의 존재 여부를 파악하면서 재귀함수로 구현하였다. 처음에 get_size 에서 ret 값을 0으로 초기화 했었는데, 생각 해보니 그렇게 하면 노드가 자기 자신도 서브 트리의 크기에 포함을 해야하므로 ret 의 초기값을 1로 수정하였다. 1234567891011121314151617181920212223242526272829303132333435363738394041.. 더보기 5170. 상원이의 직선 긋기 게임 5170. 상원이의 직선 긋기 게임 D5 치고는 굉장히 쉬운 문제였다. 일단 주어진 점의 갯수가 200개 이므로, 나올 수 있는 직선의 갯수는 200C2 로 19900 개가 된다. 따라서 모든 경우의 수를 탐색한다고 하더라도 시간 초과가 나올 수 없는 문제라서 완전탐색을 이용해서 문제를 풀었다. 2중 for문을 통해서 전체의 직선을 모두 구하고, get_incline 함수를 이용해서 직선의 기울기를 중복 생각없이 모두 vector 에 담았다. 그리고 sort 를 이용해서 vector 를 정렬하고, 중복되는 수를 빼가면서 수를 세줬다. 이때 tmp 값을 초기에 10000으로 설정한 이유는, x,y 좌표의 범위가 -1000 에서 1000 사이 이므로 기울기가 가장 클 때는 1000 이다. 따라서 1000보다.. 더보기 4676. 늘어지는 소리 만들기 4676. 늘어지는 소리 만들기 문자열을 이용한 간단한 문제였다. 하이픈이 들어가는 위치를 배열에 모두 저장해서 합산한다. ( 길이가 20까지 이므로 하이픈이 들어갈 수 있는 위치는 0~20이다) 그리고 다시 for문을 돌면서 해당하는 위치에 그 숫자만큼 입력해서 정답을 구한다. 123456789101112131415161718192021222324252627282930313233343536373839#include#includeusing namespace std; int main(){ int tc; cin >> tc; for (int t = 1; t > s; cin >> h_num; for (int i = 0; i > pos; total[pos]++; } for (int i = 0; i 더보기 4698. 테네스의 특별한 소수 4698. 테네스의 특별한 소수 에라토스테네스의 체를 이용하면 쉽게 풀 수 있는 소수 문제. main 함수가 실행하고 난 뒤에 곧바로 에라토스테네스의 체를 이용하여 모든 소수를 구할 수 있다. (이때 1은 따로 처리를 해줘야 한다) 그리고 구해진 소수 중에서 주어진 범위안의 수를 찾고, 그 수가 D라는 숫자를 포함하는지를 검사하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include#include#define MAX 1000001using namespace std; bool isPrime[MAX]; void era(){ for (int i = 2; .. 더보기 4740. 밍이의 블록게임 4740. 밍이의 블록게임 시간을 꽤나 써버린 문제이다. 기본적으로 시뮬레이션 문제에, 블록 최대 크기를 구하는 부분에서는 DFS문제를 이용했다. U,L,R,D 이 네가지 경우로 케이스를 나누어서 문제를 풀었다. U 같은 경우에는 일단 check() 함수를 통해서 배열의 맨 상단의 한줄이 비어있는지 확인하는데 사용했다. 만약 비어있다면 새로운 줄을 추가 할 수 있다는 것이고, 그렇지 않다면 새로운 줄을 추가할 수 없다. 처음에 이 부분에서 실수한 점은 맨 처음에는 can_add 라는 변수를 쓰지 않고 check() 함수를 두번 호출했는데, 그럴경우 처음 호출에서는 true 가 나왔음에도 두번째 check() 함수에서는 MOVE_UP() 함수를 통해서 밑에 한줄을 추가해서 두번째 check() 함수에서는 .. 더보기 이전 1 2 3 4 5 다음