요셉 링【dp】

1441 단어 dp
N은 한 개의 고리(1-N번)로 앉아서 첫 번째 사람부터 번호를 매기고 K를 세는 사람이 줄을 서고 뒤에 있는 사람이 다시 1부터 번호를 매긴다.마지막 남은 사람의 번호를 묻다.예: N = 3, K = 2.2번이 먼저 나열하고 그 다음은 1번, 마지막에 남은 것은 3번이다.
사고방식: 간단한 생각은 직접 추측할 수 있고 시간 복잡도 O(nk), 데이터 규모가 크면 시간을 초과할 수 있다.점차적인 사상을 운용하다.
  • 1~n 순환, 0~n-1로 간소화하여 처리하기 편리합니다.
  • 첫 번째 열에 올랐을 때 남은 k,k+1,...,n-1,0,1,...,k-2를 0,1,...,n-2로 대응하면 존재관계 f(N)=(f(N-1)+k)%N을 알 수 있다.
  • 임의의 i에 대해 f(i)=(f(i-1)+k)%i가 있음;
  • f(0) = 0;
  • 스크롤 숫자, 공간 복잡성 O(n)에서 O(1)
    • 로 감소
    #include 
using namespace std;

int main(int argc, char const *argv[])
{
    int n, k;
    cin >> n >> k;
    int ans = 0;
    for(int i = 2; i <= n; i++)
        ans = (ans + k) % i;
    cout << ans + 1 << endl; 
    return 0;
}
    2021년 최적 반응 데이터 테이블 라이브러리
    함수형 스타일 프로그래밍은 굉장합니다(동형 예제).

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage