PS 이야기

문제 및 채점: oj.uz 정점이 $N$ 개인 양방향 그래프가 있다. 이 그래프에서 정점 $i$와 정점 $j$ 사이의 단순 경로의 수는 $p[i][j]$이다. $p[i][i] = 1$이며, $0 \leq p[i][j] \leq 3$이다. $p$ 배열의 내용만 주어졌을 때, 원래 그래프를 복원하는 것이 가능한지 확인하고, 가능하다면 그래프를 복원하는 문제다. 서브태스크 1 (11 점) $p[i][j] = 1$이다. 트리에서 각 정점 사이에 경로는 항상 한 개만 존재한다는 사실을 생각해보자. 즉, 모든 트리에 대해 $p[i][j] = 1$이기 때문에, 아무 트리로 그래프를 복원하면 된다. 아래는 만들 수 있는 단순한 트리 중 하나다. 서브태스크 2 (10 점) $p[i][j] = 0\ \mathrm{or}\..

1. S OR T 스페이스(S)와 탭(T)을 입력한 순서가 주어졌을 때, 총 몇 칸 띄어지게 되었는지 구하는 문제다. 단, 탭 크기는 4다. 문자열을 입력받아서 S가 나오면 칸 수를 1 늘려주고, T가 나오면 칸 수를 현재 칸 수보다 큰 4의 배수로 만들어주면 된다. 더보기 A = input() S = 0 for c in A: S += 1 if c == 'T': while S%4 != 0: S += 1 print(S) 2. 카트라이더 별 모으기 3개의 별이 있고 각 별을 획득할 수 있는 기록 제한이 주어졌을 때, 주어진 기록이 몇 개의 별을 획득할 수 있는지 구하는 문제다. 이 문제에서 시간이 기록은 'aa:bb:cc'꼴로 주어지는데, 이 기록 문자열을 정수로 변환해도 되고, 정수로 변환하지 않고 문자열..

문제 및 채점: 사이트 A. New Elements: Part 1 질량이 X인 원소 C가 있고, 질량이 Y인 원소 J가 있다. 분자 N개가 있는데, i번째 분자에 포함된 원소 C의 개수는 C[i]개고, 포함된 원소 J의 개수는 J[i]개다. 원소 C와 원소 J 이외에 다른 원소는 포함되어 있지 않다. 분자를 질량 순서대로 정렬하려고 한다. 다만, 분자의 질량은 모두 달라야 한다. 이때, 정렬 결과로 가능한 순서는 모두 몇 개인지 구하는 문제다. 서로 다른 i와 j에 대해, C[i] ≤ C[j], J[i] ≤ J[j]를 만족하면 질량 X, Y와 상관없이 질량의 대소 관계가 명확하다. 다만, C[i] J[j]와 같이 원소 C 개수의 대소 관계와 원소 J 개수의 대소 관계가 뒤집혀있..