PAT Advanced 1049 Counting Ones(30)[수학 문제 - 단순 수학 문제]

1825 단어

제목


The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12. Input Specification: Each input file contains one test case which gives the positive N (<=230). Output Specification: For each test case, print the number of 1’s in one line. Sample Input: 12 Sample Output: 5

제목 분석


이미 하나의 정수 N을 알고 있으며, 1~N의 정수에서 1의 횟수를 구한다. (예: 11은 두 번 1의 횟수를 계산한다)

문제 풀이 사고방식


낮은 위치에서 높은 위치까지 매 비트가 1일 때의 숫자 개수를 계산하여 누적하다
  • 만약에 현재 위치가 0이고 왼쪽이 0~left-1일 때 모두 현재 위치에서 1(이때 오른쪽에서 찾을 수 있는 숫자의 총수는 0~9999...즉: a개)을 취할 수 있습니다. 현재 위치가 0이기 때문에 왼쪽에서 왼쪽을 취할 때 1을 취할 수 없습니다..
  • 현재 위치가 1이면 왼쪽이 0~left-1일 때 현재 위치에서 1(이때 오른쪽에서 찾을 수 있는 숫자의 총수는 0~9999...즉:a개)을 얻을 수 있고, 현재 위치가 1일 때 오른쪽은 0~right(즉:right 개수)만 얻을 수 있다
  • 현재 위치가 2보다 크면 왼쪽이 0~left일 때 현재 위치에서 1(이때 오른쪽에서 찾을 수 있는 숫자의 총수는 0~9999...즉: a개)을 취할 수 있다

    • 틀리기 쉬운 점

  • 1~N 숫자를 일일이 열거한 다음에 숫자 통계에 1의 횟수가 나타나면 시간을 초과한다(테스트점 4,6)

    • 지식

  • 이미 알려진 정정수는 N이고 오른쪽에서 왼쪽으로 바늘 i는 N의 어떤 위치를 가리키며 a의 현재 위치의 권중(예를 들어 i=2, a=10^2, i=0, a=10^0)
    • N/(a*10) // i 
N/a%10 // i 
N%a // i

    Code


    Code 01

    #include 
using namespace std;
/*
 4,6 
*/
int main(int argc,char * argv[]) {
    int n,t=0,a=1,left,now,right;
    scanf("%d",&n);
    while(n/a>0) {
        left = n/(a*10),now=n/a%10,right=n%a;
        if(now==0)t+=left*a;
        else if(now==1)t+=left*a+right+1;
        else t+=(left+1)*a; 
        a*=10;
    }
    printf("%d",t);
    return 0;
}
    POJ1700 Crossing River 강 건너기 문제

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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