hwooo

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 여행 경로를 각각 하나의 출발지-도착지로 봐서 모든 출발지에서의 값을 구할 수 있는 프림 알고리즘을 사용함.문제에서 보면 city[i][i]=0으로 되어 있는데 같은 도시에서 출발 도착은 가능하므로 이를 1로 바꿔줘야 한다. 코드 #include #include using namespace std; int main() { bool city[201][201] = { 0, }; vector pl..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS로 탐색하되, *2 이동은 0이므로 그 부분만 따로 계산해줌. 방문한 노드에는 현재 노드에 도착할 때까지 걸리는 시간을 저장해주고, 다음에 방문할 때 저장된 값보다 걸린 시간이 적은 경우에만 값을 갱신, 계산하도록 했다. 알고리즘이 다익스트라로 구분되었기에 우선순위 큐도 써보았는데 정렬이 필요해서인지 시간도 메모리도 더 컸다. 코드 1 - 큐 #incl..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 처음엔 이분탐색으로 시도했는데, 게시판의 예제들을 돌리면서 어떤 조건으로 설정해도 모든 경우를 충족시킬 수 없음을 확인함. 또 집터의 범위가 크지 않고, 수의 범위 또한 256으로 작은 편이라 완전 탐색으로 풂. 코드 #include int height[257]; int N, M, B; void Find(int min, int max) { int value = min - 1, high; i..

https://www.acmicpc.net/problem/10039 10039번: 평균 점수 입력은 총 5줄로 이루어져 있고, 원섭이의 점수, 세희의 점수, 상근이의 점수, 숭이의 점수, 강수의 점수가 순서대로 주어진다. 점수는 모두 0점 이상, 100점 이하인 5의 배수이다. 따라서, 평균 점 www.acmicpc.net 코드 #include int main() { int score, sum = 0; for (int i = 0; i < 5; i++) { scanf("%d", &score); if (score < 40) score = 40; sum += score; } printf("%d", sum / 5); return 0; }

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색으로 구현. 알고리즘 자체는 어렵지 않으나 사소한 것들을 놓쳐서 오래 걸림. 밑에는 풀면서 놓쳤던 오류들 - start=0으로 할 때에 mid=0이 될 수 있어 divided by zero 오류 가능성 존재. -> start=1로 선언- start=1로 둘 때 mid 값 계산 시 int형 오버플로우 가능성 존재. (채점 시 시간초과) -> start, m..

https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 풀이 계산할 때 범위가 넘어가지 않게 중간중간 나머지 연산을 시행해야 한다. 코드 #include int main() { int L, r = 31, M = 1234567891; unsigned long long result = 0, cal = 1; char c; scanf("%d\n", &L); for (int i = 0; i < L; i++) { scanf("%c", &c); // 중간중간 M..

https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 풀이 문자열로 수를 입력 받아 자릿수를 찾고, 처음과 끝에서부터 옮겨가며 값이 동일한 지 확인함. 코드 #include #include int main() { char word[6]; int s, e; bool Is_Pal; while (1) { // Input scanf("%s", word); if (word[0] == '0') break; // init s = e = 0; Is_Pal = true; while..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 BFS를 사용하여 최솟값을 구했다. 방법의 가짓수를 구하기 위해 현재 저장된 시간보다 오래 걸린 노드는 탐색하지 않았고, 계산 과정 중 여러 번 탐색되는 노드는 가장 적은 값만 저장하고, 갱신 시 큐에 삽입했다. 이 때 적거나 같은 값도 큐에 삽입해야 최소 시간의 모든 경우를 구할 수 있다.(ex. 1-> 4 : 1+1 *2 / 1*2*2) 코드 #inc..