코드19 [C] 1929: 소수 구하기 사실 이 문제가 Dynamic Programming로 푸는 것은 아니다. DP는 점화식을 이용하여 i번째까지 구한 것을 저장하고 이것을 i+1번째를 구할 때 이용하는 것이다. 사실 이걸 그대로 사용하고 있지는 않다. 다만 DP에 쓰이는 방법 일부를 사용하고 있다. i번째 수가 소수인지를 각각 구하는 것이 아니라 1부터 탐색을 할때 소수이면 그 수의 배수들을 따로 저장하여 소수인지 확인하면 된다. 즉 Bottom-up 방식으로 생각해서 구현하면 된다. #include int dp[1000001]; int main(void) { int m,n; scanf("%d %d",&m,&n); for(int i=2;i=m && i 2023. 8. 10. [C] 1004: 어린 왕자 일단 문제는 예전에 원의 방정식에서 배웠던 것 처럼 출발점과 도착점이 각각 원 안의 있냐 없냐로 최소의 행성계 진입/이탈 횟수가 정해진다. 따라서 출발지/도착지와 원의 중점 사이의 거리가 원의 반지름보다 작다면 안에 있다는 것을 알 수 있다. 여기서 주의해야할 점은 출발점과 도착점이 모두 한 원 안에 있을 수 있다는 것이다. 그래서 한 원 안에 있는 경우의 수도 뺴줘야하기 때문에 tmp1과 tmp2를 이용해 출발점과 도착점이 각각 원안에 있는지 확인한 후 두개의 합, 즉 tmp1+tmp2==1인 경우에만 cnt++를 해줌으로써 문제를 풀었다. 기억해야할 점 1. pow 함수와 sqrt 함수는 모두 double형 변수에 대해서만 연산이 가능하고 다른 연산을 할때도, 예를 들어 나눌때, 계산결과가 달라질 수.. 2023. 8. 8. [C] 9663: N-Queen 구현은 다음과 같이 진행했다. 1. 퀸이 놓이면 퀸이 공격할 수 있는 자리들에 chess배열에 1을 추가하여(색칠하여) 저장하였다. 1-1.이때 가로 세로는 그냥 칠하고 (겹치는거 빼줌), 대각선을 색칠할 때는 while문을 이용하여 색칠해줬다. 이때 색칠하는 방법은 전에 풀었던 "토마토"문제와 같이 미리 x,y좌표로 갈 수 있는 경우의 수를 배열로 저장하고 (x,y_coordinate) for문을 이용해 구현했다. 1-2 이때 그래프의 범위를 벗어나면 for문을 빠져나오도록 했다 2. 이후 빈 공간에 queen을 배치할 수 있는지 판단하고 배치 가능하면 color함수를 재귀적으로 호출한다. 2-1. 이때 계속 덧칠하면서 color을 호출했기 때문에 호출 후 return하면 다시 지워주기 위한 remov.. 2023. 8. 6. [C] 11724: 연결 요소의 개수 일단 이 문제도 결국 그래프 탐색 문제이다. 최단 거리와 관계가 없고 그냥 그래프가 서로 이어져 있냐만 확인하면 되므로 Depth-first(깊이 우선탐색)을 이용하여 인접행렬을 통해 문제를 풀었다. 여기서 유일하게 주의해야 할점은 노드가 하나라도 독립적인 연결 요소가 된다는 것이다. 그렇기 때문에 인접행렬에서 자기자신에게 가는 간선도 추가해줘야 간단히 풀 수 있다. #include int graph[1001][1001]; int visit[1001][1001]; void dfs(int n, int line, int x, int y) { for(int i=1;i 2023. 8. 6. 이전 1 2 3 4 5 다음