PS87 백준 1062 / C++ https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net [ 풀이 ] anta와 tica는 디폴트로 가르쳐야 한다. 이 5개를 제외한 글자를 가르치자. 알파벳이 26개이니 그냥 브루트포스로 21C(k-5)개를 골라주면 된다. k-5개를 골라 가르친 후에 N개의 문자열을 읽을 수 있는지 확인해주면 된다. sol 1) 그냥 모든 문자열을 순회하며 읽을 수 있는지 판별한다. 총 시간복잡도는 O(21Ck-5 * N*15)이고 이 값의 최대는 대충 21C.. 2022. 7. 15. 백준 1238 / C++ https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net [ 풀이 ] 다익스트라+가벼운 발상을 필요로 하는 문제이다. 파티장에서 집으로 최단거리는 다익 1번으로 구해진다. 그런데 집에서 파티장까지 N개는 다익스트라 N번을 해야할까? 그렇게해도 시간안엔 풀리지만 다익 1번에 구할 수 있다. 역방향 그래프도 만든후에 파티장에서 다시 다익을 돌려주면 끝. [ 코드 ] #include using namespace std; type.. 2022. 7. 13. 백준 25339 / C++ https://www.acmicpc.net/problem/25339 25339번: 반전 수와 쿼리 1부터 $N$까지의 수가 한 번씩 등장하는 수열 $P = \lbrace 1, 2, \cdots, N \rbrace$이 주어진다. 수열 $P$에 대해, $i P_j$를 만족하는 순서쌍 $(i, j)$의 개수를 $P$의 반전 수라고 정의하자. 이 www.acmicpc.net 쿼리마다 반전수의 홀짝성을 확인해주는 문제이다. 수학이 전부인 문제. [ 풀이 ] // 1번 쿼리의 경우 Ai와 Aj를 교환한다고 하자. Ai와 Aj 사이의 수열에만 관심이 있다. 나머지 A1~Ai-1, Aj+1~An은 Ai와 Aj가 교환되도 반전수에 영향이 없다. Ai+1~Aj-1중 Ai와 반전쌍을 이루는 것의.. 2022. 7. 12. 백준 1111 / C++ https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 수열이 규칙성을 만족하는지 확인하고 유일하면 출력까지 하는 문제이다. 일단 규칙이 p*전항+q 이므로 미지수가 2개이다. 따라서 a1, a2, a3만으로 p와 q는 결정된다. (항이 3개 이상일때) // 항이 3개 이상 p=(a3-a2)/(a2-a1)이 된다. p가 정수면, q도 정수이므로 a3-a2가 a2-a1의 배수인지만 체크해주자. (예외처리는 a1=a2일때) 이렇게 해서 정수 p, q를 찾았다. 이제 수열을 1번 돌면서 모두 이 규칙인지 확인한다. 잘 가다.. 2022. 7. 9. 이전 1 ··· 18 19 20 21 22 다음